# Floor in a Binary Search Tree

Problem Statement: Given a BST and a number X, find the Floor of X.
Note: Floor(X) is a number that is either equal to X or is immediately lesser than X.

If Floor could not be found, return -1.

Examples
```Example 1:
Input Format:  X = 3
Result: 3
Explanation: We find 3 in BST, so floor of 3 is 3.
Example 2:
Input Format:  X = 6
Result: 5
Explanation: We find 5 in BST, so floor of 6 is 5 as the immediate number lesser than 6 appears to be 5 in the BST.
```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

### Approach:

This Problem can be easily solved by using a similar approach as we use to Binary Search a linear array and find the number which is just lesser or equal to the given target input value.

### Algorithm:

1. We start from the root element and check whether the number whose floor we have to find out is equal to the value of the root or not. If its value is equal, we simply return the number.
2. Now, if the value of the number is not equal to the root’s value but is lesser, we can conclude by saying that the number’s floor value also lies in the left subtree of the given BST because, in BST, the left subtree contains all the elements whose values are lesser than the root element.
3. If the value of the number, however, is greater than the root’s value, then a possible floor value could be the root itself as the number is less than its value. So, to check whether the number can be increased further, we move to the right subtree and keep on updating the floor value accordingly.
4. Once, we encounter any node whose value is null, we return the computed floor value.

Dry-run: Please refer to the attached video for a detailed dry-run.

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

//Declaring the struct for Tree implementation.
struct node
{
int data;
struct node *left, *right;
};

//Defining a function for inserting new-node in BST
struct node *newNode(int data)
{
struct node *node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

int findFloor(node *root, int input)
{

int floor = -1;

while (root)
{
// If the input is already available in BST, return that.
if (root->data == input)
return input;

// If the input is greater than root, we mark floor to be root and move to
// right subtree where it may be further closer to the input value
else if (root->data < input)
{
floor = root->data;
root = root->right;
}

// Otherwise, the floor value must be in the left subtree.
else
{
root = root->left;
}
}

//Return computed floor value.
return floor;
}

int main()
{
// Driver Code.
struct node *root = newNode(10);
root->left = newNode(5);
root->left->left = newNode(4);
root->left->right = newNode(7);
root->left->right->right = newNode(8);
root->right = newNode(11);

cout << findFloor(root, 6);
cout << endl;

return 0;
}
``````

Output: 5

Time Complexity: O(log(N)) {Similar to Binary Search, at a given time we’re searching one half of the tree, so the time taken would be of the order log(N) where N are the total nodes in the BST and log(N) is the height of the tree.}

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

## Java Code

``````// Importing required packages
import java.util.*;

// Declaring the class for Tree implementation
class Node {
int data;
Node left, right;

// Constructor
Node(int item) {
data = item;
left = right = null;
}
}

public class Main {
// Function for inserting a new node in BST
static Node newNode(int data) {
Node node = new Node(data);
node.left = null;
node.right = null;
return node;
}

// Function to find floor in BST
static int findFloor(Node root, int input) {
int floor = -1;
while (root != null) {
if (root.data == input)
return input;
else if (root.data < input) {
floor = root.data;
root = root.right;
} else {
root = root.left;
}
}
return floor;
}

public static void main(String[] args) {
// Driver Code
Node root = newNode(10);
root.left = newNode(5);
root.left.left = newNode(4);
root.left.right = newNode(7);
root.left.right.right = newNode(8);
root.right = newNode(11);

System.out.println(findFloor(root, 6));
}
}
``````

Output: 5

Time Complexity: O(log(N)) {Similar to Binary Search, at a given time we’re searching one half of the tree, so the time taken would be of the order log(N) where N are the total nodes in the BST and log(N) is the height of the tree.}

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

## Python Code

``````# Defining the class for Tree implementation
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

# Function for inserting a new node in BST
def newNode(data):
node = Node(data)
node.left = None
node.right = None
return node

# Function to find floor in BST
def findFloor(root, input):
floor = -1
while root:
if root.data == input:
return input
elif root.data < input:
floor = root.data
root = root.right
else:
root = root.left
return floor

# Driver Code
root = newNode(10)
root.left = newNode(5)
root.left.left = newNode(4)
root.left.right = newNode(7)
root.left.right.right = newNode(8)
root.right = newNode(11)

print(findFloor(root, 6))
``````

Output: 5

Time Complexity: O(log(N)) {Similar to Binary Search, at a given time we’re searching one half of the tree, so the time taken would be of the order log(N) where N are the total nodes in the BST and log(N) is the height of the tree.}

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

## JavaScript Code

``````// Defining the class for Tree implementation
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}

// Function for inserting a new node in BST
function newNode(data) {
let node = new Node(data);
node.left = null;
node.right = null;
return node;
}

// Function to find floor in BST
function findFloor(root, input) {
let floor = -1;
while (root) {
if (root.data === input)
return input;
else if (root.data < input) {
floor = root.data;
root = root.right;
} else {
root = root.left;
}
}
return floor;
}

// Driver Code
let root = newNode(10);
root.left = newNode(5);
root.left.left = newNode(4);
root.left.right = newNode(7);
root.left.right.right = newNode(8);
root.right = newNode(11);

console.log(findFloor(root, 6));
``````

Output: 5

Time Complexity: O(log(N)) {Similar to Binary Search, at a given time we’re searching one half of the tree, so the time taken would be of the order log(N) where N are the total nodes in the BST and log(N) is the height of the tree.}

Space Complexity: O(1) {As no extra space is being used, we’re just traversing the BST.}

Video Explanation