☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Floor in a Binary Search Tree

Easy TUF ID 2778 A2Z

Java source ↗ Edit this article ↗

Problem

Given the root of a binary search tree and an integer x, return the floor of x: the largest key in the tree that is less than or equal to x. If every key is larger than x, return -1. Keys are non-negative, so -1 is never a real key.

Constraints: up to 10^5 nodes; keys and x are between 0 and 10^9.

Example 1

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

x = 11   answer = 10

The keys not above 11 are 2, 4, 6, 8, 10; the largest is 10.

Example 2

same tree, x = 1   answer = -1

The smallest key is 2, which is already above 1.

If x itself is in the tree, the answer is x.

Approach 1: Brute force, look at every node

Intuition. The floor is “the maximum over all keys that are <= x”. Without using the ordering, we can visit every node, keep the ones that qualify and take the largest. Because keys are non-negative, -1 works as “nothing found yet”: it loses to every real key in a max.

Algorithm.

  1. For an empty subtree, return -1.
  2. The node’s own contribution is its key if key <= x, otherwise -1.
  3. Return the maximum of that, the floor found in the left subtree, and the floor found in the right subtree.
static int bruteForce(TreeNode root, int x) {
    if (root == null) return -1;
    int best = root.val <= x ? root.val : -1;
    best = Math.max(best, bruteForce(root.left, x));
    best = Math.max(best, bruteForce(root.right, x));
    return best;
}

Complexity. Time O(n): every node is visited. Space O(h) for the recursion stack.

Approach 2: Recursive descent using the BST property

Intuition. Compare x with the root.

Each call discards one subtree, so only one path is explored.

Algorithm.

  1. If the node is null, return -1.
  2. If root.val == x, return x.
  3. If root.val > x, return the floor of the left subtree.
  4. Otherwise compute closer = floor of the right subtree; return closer if it is not -1, else root.val.
static int recursive(TreeNode root, int x) {
    if (root == null) return -1;
    if (root.val == x) return x;
    if (root.val > x) return recursive(root.left, x);     // root and its right subtree are all too big
    int closer = recursive(root.right, x);               // root fits; something closer may be on its right
    return closer != -1 ? closer : root.val;
}

Complexity. Time O(h), Space O(h) for the recursion stack.

Approach 3: Optimal, iterative descent

Intuition. Turn the recursion into a loop by carrying the “best candidate so far” forward instead of combining answers on the way back. Walk down from the root. Whenever cur.val < x, cur is a valid floor, so record it and move right to look for something closer. Whenever cur.val > x, move left. Stop on an exact match or when the walk falls off the tree.

Why is it enough to overwrite the candidate instead of taking a maximum? After recording cur.val we move into the right subtree of cur, and every key there is larger than cur.val. So each newly recorded candidate is larger than all previous ones, which makes the latest candidate the best.

Algorithm.

  1. Set floor = -1 and cur = root.
  2. While cur is not null:
    • if cur.val == x, return x;
    • if cur.val < x, set floor = cur.val and move right;
    • otherwise move left.
  3. Return floor.
static int optimal(TreeNode root, int x) {
    int floor = -1;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == x) return x;
        if (cur.val < x) {
            floor = cur.val;                         // candidate; every later candidate is larger
            cur = cur.right;
        } else {
            cur = cur.left;
        }
    }
    return floor;
}

Dry run on Example 1 with x = 11:

cur comparison action floor
8 8 < 11 record, go right 8
12 12 > 11 go left 8
10 10 < 11 record, go right 10
null   stop 10

And with x = 1: at 8 go left, at 4 go left, at 2 go left, fall off. No candidate was ever recorded, so the answer is -1.

Complexity. Time O(h), which is O(log n) for a balanced tree and O(n) for a chain. Space O(1).

On a sorted array the floor is found with binary search: keep the last index whose value is <= x while halving the range. The tree walk is the same algorithm. The current node is the “middle”, its left subtree is the lower half, its right subtree the upper half, and recording a candidate before moving right is exactly “remember this index, then search the right half”. The only difference is that a tree’s halves may be unequal in size, which is why the cost is the height rather than log2 n.

Edge cases and pitfalls