Ceil in a BST

Ceil in a BST is a clean little tree problem that rewards you for actually using the binary-search-tree ordering instead of treating the tree like a plain bag of numbers. The whole solution is one walk from the root to a leaf.

The slow way first

The obvious idea: collect every value in the tree, then scan for the smallest one that is >= key. An in-order traversal visits all n nodes and gives them in sorted order, so that is O(n) time and O(n) space for the list. It works, but it throws away the very thing that makes a BST special — its ordering.

The question to ask: at any node, do I even need to look at both subtrees? In a BST, no. The ordering tells me which way to go.

The idea: let the ordering steer you

Walk down from the root, keeping the best candidate seen so far. At each node:

• If node.val >= key, this node qualifies as a ceil. Record it, then go left — anything smaller that still qualifies can only be in the left subtree.
• If node.val < key, this node is too small to ever be the ceil, so go right to find larger values.

When you walk off the tree (hit None), the last value you recorded is the answer.

Because we always move to exactly one child, the whole thing is a single root-to-leaf path — no recursion stack, no backtracking.

Walk through it

Step through the animation. The node pointer rides the current node. At 8 (>= 5) we record 8 and go left. At 4 (< 5) we go right, candidate unchanged. At 6 (>= 5) we record the better candidate 6 and go left. At 5 (>= 5) we record 5 and go left, but 5 has no left child, so node becomes None and we stop. The last candidate, 5, is the answer.

Pseudocode

ceil = None
node = root
while node is not None:
    if node.val >= key:
        ceil = node.val        # candidate: smallest qualifying so far
        node = node.left       # try for something even closer to key
    else:
        node = node.right      # node too small, larger values are right
return ceil

The Python solution

def find_ceil(root, key):
    ceil = None
    node = root
    while node is not None:
        if node.val >= key:
            ceil = node.val
            node = node.left
        else:
            node = node.right
    return ceil

• ceil holds the best candidate found so far, starting as None.
• We walk with node, beginning at the root.
• Lines 5 to 7 are the heart: when node.val >= key, this value qualifies, so we record it and steer left toward smaller qualifying values.
• The else branch handles node.val < key: the node cannot be the ceil, so we go right for larger values.
• When node becomes None, the loop ends and the last recorded ceil is returned.

Complexity

Here h is the height of the tree — O(log n) if it is balanced, O(n) in the worst (degenerate) case. The iterative walk uses only a couple of variables, so extra space is O(1).

When this pattern shows up

Practice