Binary Search Tree

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.

Practice:
Solve Problem code-studio

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

Special thanks to Priyanshi Goel for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article