Find the floor in a BST

Given a binary search tree (BST) and a target value x, write a program to find the floor of x in the BST. The floor of x is the largest element in the BST that is smaller than or equal to x. If no such element exists, return -1.

Input/Output Examples

plaintext
Example 1:
Input:

       8
      / \
     4   12
    / \  / \
   2   6 10 14

x = 5
Output: 4
Explanation: The largest value smaller than or equal to 5 in the BST is 4.

Example 2:
Input:

       8
      / \
     4   12
    / \  / \
   2   6 10 14

x = 13
Output: 12
Explanation: The largest value smaller than or equal to 13 in the BST is 12.

Example 3:
Input:

       8
      / \
     4   12
    / \  / \
   2   6 10 14

x = 1
Output: -1
Explanation: There is no value smaller than or equal to 1 in the BST.

Approach to Find the Floor in a BST

  1. Binary Search Tree Property:
    • In a BST, for any node N, all nodes in its left subtree are smaller than N, and all nodes in its right subtree are larger than N.
    • This property allows us to efficiently search for the floor value by traversing the tree.
  2. Recursive or Iterative Approach:
    • Start from the root of the tree.
    • If the value of the current node is equal to x, then x is the floor.
    • If the value of the current node is less than or equal to x, the current node may be the floor, but there might be a larger value in the right subtree that is still smaller than or equal to x. Thus, move to the right subtree and keep track of the current node.
    • If the value of the current node is greater than x, move to the left subtree, as the floor must be in the left subtree.
    • If no such value is found, return -1.

C++ Program to Find the Floor in a BST

cpp
#include <iostream>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Function to find the floor value in a BST
int findFloor(TreeNode* root, int x) {
    int floor = -1;

    while (root != NULL) {
        if (root->data == x) {
            return root->data;
        }

        // If the current node's value is smaller than or equal to x, it could be the floor
        if (root->data < x) {
            floor = root->data;
            root = root->right;
        }
        // Move to the left subtree if the current node's value is greater than x
        else {
            root = root->left;
        }
    }

    return floor;
}

int main() {
    // Create a sample BST
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(4);
    root->right = new TreeNode(12);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(6);
    root->right->left = new TreeNode(10);
    root->right->right = new TreeNode(14);

    int x = 5;
    int floorValue = findFloor(root, x);

    if (floorValue != -1) {
        cout << "Floor of " << x << " in the BST is: " << floorValue << endl;
    } else {
        cout << "Floor not found for " << x << " in the BST." << endl;
    }

    return 0;
}

Java Program to Find the Floor in a BST

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class FloorInBST {

    // Function to find the floor value in a BST
    public static int findFloor(TreeNode root, int x) {
        int floor = -1;

        while (root != null) {
            if (root.data == x) {
                return root.data;
            }

            // If the current node's value is smaller than or equal to x, it could be the floor
            if (root.data < x) {
                floor = root.data;
                root = root.right;
            }
            // Move to the left subtree if the current node's value is greater than x
            else {
                root = root.left;
            }
        }

        return floor;
    }

    public static void main(String[] args) {
        // Create a sample BST
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(4);
        root.right = new TreeNode(12);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(6);
        root.right.left = new TreeNode(10);
        root.right.right = new TreeNode(14);

        int x = 5;
        int floorValue = findFloor(root, x);

        if (floorValue != -1) {
            System.out.println("Floor of " + x + " in the BST is: " + floorValue);
        } else {
            System.out.println("Floor not found for " + x + " in the BST.");
        }
    }
}

Python Program to Find the Floor in a BST

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to find the floor value in a BST
def find_floor(root, x):
    floor = -1

    while root:
        if root.data == x:
            return root.data

        # If the current node's value is smaller than or equal to x, it could be the floor
        if root.data < x:
            floor = root.data
            root = root.right
        # Move to the left subtree if the current node's value is greater than x
        else:
            root = root.left

    return floor

# Example usage
if __name__ == "__main__":
    # Create a sample BST
    root = TreeNode(8)
    root.left = TreeNode(4)
    root.right = TreeNode(12)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(6)
    root.right.left = TreeNode(10)
    root.right.right = TreeNode(14)

    x = 5
    floor_value = find_floor(root, x)

    if floor_value != -1:
        print(f"Floor of {x} in the BST is: {floor_value}")
    else:
        print(f"Floor not found for {x} in the BST.")
  • Time Complexity: O(h), where h is the height of the binary search tree. In the worst case, this could be O(n) for a skewed tree, but for a balanced BST, it is O(log n).
  • Space Complexity: O(1) for the iterative approach, as no extra space is required other than variables.

DSA

6569

601

Related Articles