☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Floor in a BST

Easy TUF ID 2779 SDE

Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree and an integer x. Return the floor of x in the tree: the largest key that is less than or equal to x. If every key in the tree is greater than x (or the tree is empty), return -1. Keys are non-negative, so -1 can never be confused with a real key.

The tree is a standard BST: for every node, all keys in its left subtree are smaller than it and all keys in its right subtree are larger.

Constraints: up to 10^5 nodes; keys and x lie between 0 and 10^9. The tree is not guaranteed to be balanced, so its height h can be anything from log n to n.

Example 1

          10
        /    \
       5      15
      / \    /  \
     2   8  12   20

x = 13   answer = 12

The keys not above 13 are 2, 5, 8, 10, 12; the largest of them is 12.

Example 2

same tree, x = 1   answer = -1

Every key is larger than 1, so there is no floor.

Approach 1: Brute force, read the sorted order

Intuition. An in-order traversal of a BST (left subtree, node, right subtree) lists the keys in ascending order. Once we have that sorted list, the floor is simply the last key that does not exceed x. We can stop scanning at the first key that is too big, because everything after it is bigger still.

This approach is correct, but it touches every node to answer a question about one position in the order. It ignores the fact that the BST shape already tells us which half of the keys to skip at each node.

Algorithm.

  1. Do an in-order traversal and append each key to a list. The list is sorted.
  2. Walk the list from the start, remembering the most recent key that is <= x.
  3. Stop at the first key > x. Return the remembered key, or -1 if there was none.
static int bruteForce(TreeNode root, int x) {
    List<Integer> sorted = new ArrayList<>();
    inorder(root, sorted);
    int floor = -1;
    for (int key : sorted) {
        if (key > x) break;                  // sorted: every later key is too big as well
        floor = key;
    }
    return floor;
}

static void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);
    out.add(node.val);
    inorder(node.right, out);
}

Complexity. Time O(n): the traversal visits every node once and the scan is at most n steps. Space O(n) for the list, plus O(h) recursion stack.

Approach 2: Better, recursive descent

Intuition. Look at the root and compare it with x.

Each step discards one entire subtree, which is exactly what makes binary search fast on a sorted array. The BST is that sorted array arranged as a decision tree.

Algorithm.

  1. If the node is null, return -1.
  2. If its key equals x, return x.
  3. If its key is greater than x, return the floor from the left child.
  4. Otherwise get the floor from the right child; return it if it is not -1, else return the node’s key.
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 whole right subtree are too big
    int closer = recursive(root.right, x);              // root fits; anything closer must be on its right
    return closer != -1 ? closer : root.val;
}

Complexity. Time O(h): one node per level is examined. Space O(h) for the recursion stack, which on a degenerate (chain-shaped) tree of 10^5 nodes can be deep enough to overflow Java’s default stack.

Approach 3: Optimal, iterative descent with a running candidate

Intuition. The recursion in Approach 2 only ever goes down one path and never needs to come back up except to fall back on “the last node where we went right”. So we can replace the call stack with a single variable floor that remembers that node.

Why does overwriting floor never lose a better answer? We only move right from a candidate, and every key in the right subtree of a candidate is larger than it. So each new candidate is strictly larger than the previous one, while still being <= x. The last candidate recorded is therefore the largest one, which is exactly the floor.

The invariant to hold in your head: the floor of x is either the current value of floor or some key in the subtree rooted at cur. It holds at the start (floor = -1, cur = root), each step preserves it, and when cur becomes null the subtree is empty, so floor is the answer.

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 to cur.right.
    • Otherwise move to cur.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;          // cannot do better than an exact match
        if (cur.val < x) {
            floor = cur.val;                 // a candidate, and larger than every earlier candidate
            cur = cur.right;                 // look for a bigger key that still fits
        } else {
            cur = cur.left;                  // too big: the floor can only be on the left
        }
    }
    return floor;
}

Dry run on Example 1 with x = 13:

cur comparison action floor
10 10 < 13 record, go right 10
15 15 > 13 go left 10
12 12 < 13 record, go right 12
null   stop 12

Notice that 10 was a perfectly valid floor, but the walk kept going because a closer key might exist on its right, and it did.

With x = 11 the walk records 10, goes right to 15, then left to 12, then left again to null. The answer is 10, the root itself, even though we finished at a leaf. This is the case that trips people who think “return the last node visited”.

Complexity. Time O(h): one comparison per level. Space O(1): two variables. On a balanced tree h is about log n, so a tree of a million keys needs about twenty comparisons.

Edge cases and pitfalls