☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Floor and Ceil in a BST

Easy TUF ID 107 A2Z

Java source ↗ Edit this article ↗

Problem

Given the root of a binary search tree and an integer key, find:

Return them as {floor, ceil}. If no key qualifies for one of them, report -1 for it. As in the usual judge versions, keys are non-negative, so -1 cannot be confused with a real key.

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

Example 1

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

key = 11   answer = {10, 12}

10 is the largest key not above 11, and 12 is the smallest key not below 11.

Example 2

same tree, key = 1   answer = {-1, 2}

Every key is above 1, so there is no floor; the smallest key, 2, is the ceil. If key is in the tree, both answers equal key.

Approach 1: Brute force, scan the sorted keys

Intuition. An inorder traversal of a BST lists the keys in increasing order. On a sorted list, the floor is the last value that is <= key and the ceil is the first value that is >= key. One pass over the list finds both. This is simple and obviously correct, but it touches every node and stores every key, even though only a few of them can matter.

Algorithm.

  1. Collect the keys with an inorder traversal into sorted.
  2. Start with floor = -1, ceil = -1.
  3. For each value v in order: if v <= key, set floor = v (later values overwrite earlier ones, so the last one wins); if v >= key and no ceil has been set yet, set ceil = v.
  4. Return {floor, ceil}.
static int[] bruteForce(TreeNode root, int key) {
    List<Integer> sorted = new ArrayList<>();
    inorder(root, sorted);
    int floor = -1, ceil = -1;
    for (int v : sorted) {
        if (v <= key) floor = v;                     // the last value <= key wins
        if (v >= key && ceil == -1) ceil = v;        // the first value >= key wins
    }
    return new int[]{floor, ceil};
}

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) for the traversal and the scan. Space O(n) for the list, plus O(h) recursion.

Once the keys are in a sorted list you could binary search instead of scanning, but building the list already costs O(n), so that would not change the total.

Approach 2: Optimal, walk down from the root

Intuition for the floor. Stand at a node cur and compare it with key.

The walk never needs to backtrack, because each comparison rules out one whole subtree. Better still, every candidate we record is larger than the previous one: after recording cur.val we only ever move into the right subtree of cur, where all keys exceed cur.val. So the most recent candidate is always the best, and a plain assignment is enough; no max is needed.

Intuition for the ceil. It is the mirror image. A node with cur.val < key is too small together with its whole left subtree, so go right. A node with cur.val > key is a candidate, and anything closer to key must be smaller, so record it and go left.

Algorithm.

  1. findFloor: floor = -1, cur = root. While cur is not null: return key on an exact match; if cur.val < key, set floor = cur.val and go right; otherwise go left. Return floor.
  2. findCeil: ceil = -1, cur = root. While cur is not null: return key on an exact match; if cur.val > key, set ceil = cur.val and go left; otherwise go right. Return ceil.
  3. Return {findFloor(root, key), findCeil(root, key)}.
static int[] optimal(TreeNode root, int key) {
    return new int[]{findFloor(root, key), findCeil(root, key)};
}

static int findFloor(TreeNode root, int key) {
    int floor = -1;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == key) return key;
        if (cur.val < key) {
            floor = cur.val;                         // a candidate; anything closer is to its right
            cur = cur.right;
        } else {
            cur = cur.left;                          // too big, and so is its whole right subtree
        }
    }
    return floor;
}

static int findCeil(TreeNode root, int key) {
    int ceil = -1;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == key) return key;
        if (cur.val > key) {
            ceil = cur.val;                          // a candidate; anything closer is to its left
            cur = cur.left;
        } else {
            cur = cur.right;                         // too small, and so is its whole left subtree
        }
    }
    return ceil;
}

Dry run on Example 1 with key = 11:

walk cur comparison action best so far
floor 8 8 < 11 record, go right 8
floor 12 12 > 11 go left 8
floor 10 10 < 11 record, go right 10
floor null   stop 10
ceil 8 8 < 11 go right -1
ceil 12 12 > 11 record, go left 12
ceil 10 10 < 11 go right 12
ceil null   stop 12

Notice that the two walks visit exactly the same nodes. Both go left when cur.val > key and right when cur.val < key, which is the search path of key. So the floor and the ceil are always the closest keys on either side of that path, and the two loops could be fused into one. They are kept separate here because each is useful on its own.

Complexity. Time O(h) for each walk, so O(h) overall: O(log n) for a balanced tree, O(n) for a chain. Space O(1).

Edge cases and pitfalls