Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Floor in BST

EASYProblemSolveExternal Links

Description

Given a Binary Search Tree (BST) and an integer x, find the floor of x in the BST.

The floor of x is defined as the greatest value in the tree that is less than or equal to x. In other words, among all nodes whose values do not exceed x, the floor is the one with the maximum value.

If no node in the BST has a value less than or equal to x, return -1.

Examples

Example 1

Input:

       8
      / \
     5   9
    / \    \
   2   6   10

x = 3

Output: 2

Explanation: The values in the BST that are less than or equal to 3 are: {2}. The only qualifying value is 2, so the floor of 3 is 2. Nodes 5, 6, 8, 9, and 10 are all larger than 3 and cannot be the floor.

Example 2

Input:

       3
      / \
     2   5
        / \
       4   7
      /
     3

x = 1

Output: -1

Explanation: The smallest value in the BST is 2. Since no node has a value less than or equal to 1, the floor does not exist and we return -1.

Example 3

Input:

       8
      / \
     5   9
    / \    \
   2   6   10

x = 7

Output: 6

Explanation: The values in the BST that are less than or equal to 7 are: {2, 5, 6}. Among these, 6 is the greatest, making it the floor of 7. Even though 8 is close to 7, it exceeds 7 and therefore does not qualify.

Constraints

  • 1 ≤ Number of nodes ≤ 10^5
  • 1 ≤ x, Value of nodes ≤ 10^6

Editorial

Brute Force

Intuition

The simplest way to find the floor is to treat the BST like an ordinary collection of numbers. If we gather all the values into a sorted list (using the BST's inorder traversal property), the floor of x is simply the last value in that list that does not exceed x.

Picture a shelf of books ordered by page count from left to right. To find the floor of 150 pages, you slide your finger along from left to right, passing each book that has 150 or fewer pages. The moment you reach a book with more than 150 pages, you stop. The book your finger was on just before stopping is the answer — the one with the most pages that still does not exceed your limit.

Step-by-Step Explanation

Let us trace through the algorithm using the BST from Example 3 with x = 7:

Step 1: Perform an inorder traversal of the BST. Visiting nodes in left → root → right order yields all values in ascending order.

  • Inorder result: [2, 5, 6, 8, 9, 10]

Step 2: Scan the sorted array from left to right, keeping track of the largest value seen so far that is ≤ 7.

  • Check arr[0] = 2. Is 2 ≤ 7? Yes. Update floor = 2.

Step 3: Check arr[1] = 5. Is 5 ≤ 7? Yes. Update floor = 5 (5 is larger than 2 while still being ≤ 7, so it is a tighter floor).

Step 4: Check arr[2] = 6. Is 6 ≤ 7? Yes. Update floor = 6 (even tighter than 5).

Step 5: Check arr[3] = 8. Is 8 ≤ 7? No. Since the array is sorted, all remaining values (9, 10) are also greater than 7. We can stop scanning immediately.

Step 6: Return floor = 6. This is the greatest value in the BST that does not exceed 7.

Scanning Sorted Inorder Array for Floor of 7 — After performing inorder traversal to get sorted values, we scan left to right, updating the floor candidate whenever we find a value that is less than or equal to x.

Algorithm

  1. Perform an inorder traversal of the BST to collect all node values into a sorted array
  2. Initialize floor = -1
  3. Scan the sorted array from left to right:
    • If the current value is ≤ x, update floor to this value (it is the best candidate seen so far)
    • If the current value is > x, stop — all remaining values are also > x due to sorted order
  4. Return floor

Code

#include <vector>
using namespace std;

// Collect all node values in sorted order via inorder traversal
void inorder(Node* node, vector<int>& result) {
    if (node == nullptr) return;
    inorder(node->left, result);
    result.push_back(node->data);
    inorder(node->right, result);
}

int findFloor(Node* root, int x) {
    vector<int> sorted;
    inorder(root, sorted);
    
    int floor = -1;
    for (int val : sorted) {
        if (val <= x) {
            floor = val;  // Keep updating with the latest (largest) value <= x
        } else {
            break;  // All remaining values exceed x
        }
    }
    return floor;
}
def findFloor(root, x):
    sorted_vals = []
    
    # Inorder traversal gives sorted values for a BST
    def inorder(node):
        if node is None:
            return
        inorder(node.left)
        sorted_vals.append(node.data)
        inorder(node.right)
    
    inorder(root)
    
    floor = -1
    for val in sorted_vals:
        if val <= x:
            floor = val  # Update with the largest qualifying value so far
        else:
            break  # Sorted order guarantees no more valid values
    return floor
import java.util.ArrayList;
import java.util.List;

int findFloor(Node root, int x) {
    List<Integer> sorted = new ArrayList<>();
    inorder(root, sorted);
    
    int floor = -1;
    for (int val : sorted) {
        if (val <= x) {
            floor = val;  // Keep updating with largest value <= x
        } else {
            break;  // Remaining values all exceed x
        }
    }
    return floor;
}

void inorder(Node node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);
    result.add(node.data);
    inorder(node.right, result);
}

Complexity Analysis

Time Complexity: O(n)

The inorder traversal visits every node in the BST exactly once, taking O(n) time. The subsequent scan over the sorted array takes up to O(n) in the worst case (when all values are ≤ x). Combined, the total time is O(n) + O(n) = O(n).

Space Complexity: O(n)

We store all n node values in an auxiliary array. The recursion stack for the inorder traversal also uses O(h) space where h is the tree height. Since h ≤ n, the dominant space cost is the O(n) array.

Why This Approach Is Not Efficient

The brute force approach visits every node in the tree and stores all values in an auxiliary array. For a BST with up to 10^5 nodes, this means 10^5 visits, 10^5 entries in the array, and up to 10^5 comparisons during the scan.

The critical waste is that we treat the BST as if it were an unstructured bag of numbers. A BST is fundamentally a decision tree — at every node, the left subtree holds smaller values and the right subtree holds larger values. This built-in ordering means we can make an informed binary choice at each level: if the current node is too large, we know the answer lies in the left half. If it is a valid floor candidate, a tighter answer might exist in the right half.

By following a single path from root toward a leaf, we reduce the number of visited nodes from n to at most h (the tree height). We also eliminate the need for any auxiliary array, dropping space from O(n) to O(1).

Optimal Approach - Iterative BST Traversal

Intuition

Rather than gathering all values first, we navigate the BST directly by asking one question at each node: is this node small enough to be a floor candidate? The BST property lets us prune half the tree at each step.

Starting from the root, we apply a simple rule:

  • If the current node's value equals x: We found the exact floor — no larger valid value exists. Return immediately.
  • If the current node's value is greater than x: This node is too large. Its entire right subtree holds even larger values, so they are all irrelevant. Move to the left child where smaller values live.
  • If the current node's value is less than x: This node is a valid floor candidate (it is ≤ x). But a larger valid value might exist in the right subtree. Record this node as our best answer so far and move to the right child to search for a tighter match.

We keep descending until we hit a null pointer, at which point the last recorded candidate is our answer.

Think of searching for the most expensive item you can afford in a department store where aisles are sorted by price. If you find an aisle priced at 30andyourbudgetis30 and your budget is 50, you note it as affordable and move right to the more expensive aisles. If you find an aisle at $60 (over budget), you move left. Eventually, you settle on the most expensive aisle within budget without checking every single aisle.

Step-by-Step Explanation

Let us trace through the algorithm using the BST from Example 3 with x = 7:

Step 1: Start at the root node (value 8). Initialize floor = -1.

  • Compare: x = 7 vs node = 8. Since 7 < 8, node 8 is too large to be the floor.
  • Do not update floor. Move to the left child where smaller values reside.

Step 2: Current node is 5.

  • Compare: x = 7 vs node = 5. Since 7 > 5, node 5 is ≤ x and qualifies as a floor candidate.
  • Update floor = 5. Move to the right child to search for a larger valid value.

Step 3: Current node is 6.

  • Compare: x = 7 vs node = 6. Since 7 > 6, node 6 is ≤ x and is a better candidate than 5.
  • Update floor = 6. Move to the right child.

Step 4: Node 6 has no right child — we reach null. No more nodes to explore.

Step 5: Return floor = 6. We visited only 3 nodes (8 → 5 → 6) out of 6 total, following a single path through the tree. Nodes 2, 9, and 10 were never examined.

Floor in BST — Iterative Traversal for x = 7 — Watch how the BST property guides us along a single path from root, updating the floor candidate whenever we find a node ≤ x and pruning subtrees that cannot contain the answer.

Algorithm

  1. Initialize floor = -1 (no candidate found yet)
  2. While the current node is not null:
    • If current node's value equals x → return x (exact match, tightest possible floor)
    • If x > current node's value → update floor to current node's value, move to right child (search for a larger valid candidate)
    • If x < current node's value → move to left child (current value is too large)
  3. Return floor

Code

int findFloor(Node* root, int x) {
    int floor = -1;
    
    while (root != nullptr) {
        // Exact match is the tightest possible floor
        if (root->data == x) {
            return x;
        }
        
        if (x > root->data) {
            // Current node <= x, record as candidate
            floor = root->data;
            // Search right for a larger valid value
            root = root->right;
        } else {
            // Current node > x, need a smaller value
            root = root->left;
        }
    }
    
    return floor;
}
def findFloor(root, x):
    floor = -1
    
    while root is not None:
        # Exact match is the tightest possible floor
        if root.data == x:
            return x
        
        if x > root.data:
            # Current node <= x, record as candidate
            floor = root.data
            # Search right for a larger valid value
            root = root.right
        else:
            # Current node > x, need a smaller value
            root = root.left
    
    return floor
int findFloor(Node root, int x) {
    int floor = -1;
    
    while (root != null) {
        // Exact match is the tightest possible floor
        if (root.data == x) {
            return x;
        }
        
        if (x > root.data) {
            // Current node <= x, record as candidate
            floor = root.data;
            // Search right for a larger valid value
            root = root.right;
        } else {
            // Current node > x, need a smaller value
            root = root.left;
        }
    }
    
    return floor;
}

Complexity Analysis

Time Complexity: O(h), where h is the height of the BST

At each step we descend one level in the tree, making at most h comparisons before reaching a null pointer. For a balanced BST, h = O(log n), giving us logarithmic search time. For a skewed BST (degenerating into a linked list), h = O(n), which is as slow as linear search. On average for a random BST, h ≈ O(log n).

Space Complexity: O(1)

We use only a single integer variable (floor) and a pointer to traverse the tree. No auxiliary data structures and no recursion stack are required. The space usage is constant regardless of the number of nodes.