Topics › Binary Search Trees › Practice Problems

Ceil in a BST

Easy TUF ID 2777 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the root of a binary search tree and an integer x. Return the ceil of x in the tree: the smallest key that is greater than or equal to x. If every key is smaller than x (or the tree is empty), return -1. Keys are non-negative, so -1 can never be mistaken for 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 may be unbalanced, so its height h ranges from about log n up to n.

Example 1

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

x = 13   answer = 15

The keys not below 13 are 15 and 20; the smallest is 15.

Example 2

same tree, x = 21   answer = -1

Every key is smaller than 21, so there is no ceil.

Approach 1: Brute force, read the sorted order

Intuition. An in-order traversal of a BST (left, node, right) produces the keys in ascending order. In a sorted list, the ceil of x is the first key that is at least x. So: flatten, then scan from the left and stop at the first key that is large enough.

It works, but it visits every node to answer a question that only concerns one spot in the order. The BST’s shape could have told us at every node which half to ignore.

Algorithm.

1. Do an in-order traversal, appending each key to a list. The list is sorted.
2. Scan the list from the start.
3. Return the first key that is >= x. If the scan finishes, return -1.

static int bruteForce(TreeNode root, int x) {
    List<Integer> sorted = new ArrayList<>();
    inorder(root, sorted);
    for (int key : sorted) {
        if (key >= x) return key;            // first key that is large enough
    }
    return -1;
}

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): every node is visited 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. Compare the root with x.

• If root.val == x, the ceil is x itself; nothing can be closer.
• If root.val < x, the root is too small, and so is its entire left subtree (those keys are smaller still). The answer, if any, is in the right subtree.
• If root.val > x, the root is a valid ceil candidate. Every key in its right subtree is larger than the root, so none of them can beat it. Only the left subtree might hold a key that is still >= x but closer to it. Ask the left subtree for its ceil; if it has one, use it, otherwise the root is the answer.

Every comparison throws away a whole subtree, which is binary search expressed on a tree.

Algorithm.

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

Complexity. Time O(h): one node per level. Space O(h) for the recursion, which for a chain-shaped tree of 10^5 nodes can overflow Java’s default thread stack.

Approach 3: Optimal, iterative descent with a running candidate

Intuition. Approach 2 walks a single root-to-leaf path. The only thing it needs from the way back up is “the last node where we turned left”, because that is the node it falls back on. A single variable can hold that, which removes the recursion entirely.

Why is it safe to overwrite ceil each time we turn left? We only move left from a candidate, and every key in a candidate’s left subtree is smaller than it. So each newly recorded candidate is strictly smaller than the previous one while still being >= x. The last one recorded is the smallest such key: the ceil.

The invariant: the ceil of x is either the current ceil or a key in the subtree rooted at cur. It is true at the start, every step keeps it true, and when cur falls off the tree the subtree is empty, so ceil must be the answer.

Algorithm.

1. Set ceil = -1 and cur = root.
2. While cur is not null:
   • If cur.val == x, return x.
   • If cur.val > x, set ceil = cur.val and move to cur.left.
   • Otherwise move to cur.right.
3. Return ceil.

static int optimal(TreeNode root, int x) {
    int ceil = -1;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == x) return x;          // cannot do better than an exact match
        if (cur.val > x) {
            ceil = cur.val;                  // a candidate, and smaller than every earlier candidate
            cur = cur.left;                  // look for a smaller key that is still large enough
        } else {
            cur = cur.right;                 // too small: the ceil can only be on the right
        }
    }
    return ceil;
}

Dry run on Example 1 with x = 13:

Now try x = 9. The root 10 is recorded, then the walk goes left to 5 (too small, go right), then to 8 (too small, go right) and falls off the tree. The answer is 10, the root, even though the walk ended near the bottom of the left subtree. “Return the last node visited” is the classic wrong answer here.

Complexity. Time O(h): one comparison per level. Space O(1). For a balanced tree with a million keys that is about twenty comparisons.

Edge cases and pitfalls

• Empty tree. The loop does not run and -1 comes back. The recursive version must test null before reading root.val.
• x larger than every key. The walk only goes right and never records anything, so the answer is -1.
• x smaller than every key. The walk only goes left, recording each node on the way, so it finishes with the minimum key.
• Exact match. Return at once; nothing can be closer.
• Key 0. A ceil of 0 is a real answer (for x = 0). The -1 sentinel relies on keys being non-negative. With negative keys, return an Integer (with null for “none”) instead.
• Strict vs non-strict. Ceil uses >=. The in-order successor uses a strict >. Using the wrong one changes the answer whenever x is itself a key.
• Skewed trees. On a chain h = n. The iterative version uses constant space regardless; the recursive one can overflow the stack.
• Overflow. The algorithm only compares keys, so no arithmetic can overflow.

Related problems

• Floor in a BST is the mirror image: record when going right instead of left.
• Floor and Ceil in a BST computes both values with the same walk.
• Floor and Ceil in Sorted Array solves the array version with binary search.
• Search in a Binary Search Tree is the same descent without a running candidate.
• Inorder Successor/Predecessor in BST is the strict version of ceil and floor for a key that is in the tree.