Ceil in BST
Ceil in BST: smallest BST value ≥ x (the ceiling), or −1 if none.
- 1 <= number of nodes <= 10⁵
- 1 <= node value, x <= 10⁹
- Return -1 when no value is >= x
Intuition
Finding the ceil in BST means finding the smallest value that is still greater than or equal to x. The obvious approach is to collect every node into a sorted list and scan it, but that throws away the one thing a BST gives you for free: at every node, you already know which half of the remaining tree can possibly hold the answer.
Think about standing at some node with value v and comparing it to x. If v < x, then v is too small to be a ceiling, and so is every value in its left subtree, because a BST keeps smaller values on the left. That single comparison eliminates the node and everything beneath it on one side. The only place a ceiling can still live is to the right.
The interesting case is v ≥ x. Now v is a legitimate answer — it clears the bar. But it may not be the smallest value that clears it, because the left subtree could hold something between x and v. So you do two things at once:
- Record v as the best answer so far, then move left anyway to try to beat it.
That is the whole idea. You never backtrack and you never compare a node twice. Each step either discards a subtree or tightens the answer, so the walk goes straight down and the recorded candidate only ever improves. If you finish at a null pointer having recorded nothing, no value ever cleared x, and the answer is −1.
Find ceil in bst and floor share one shape: you're looking for the best value on one side of x, so you keep a candidate and keep trying to improve it. Whenever a search can't hit exactly and must settle for the nearest, the pattern is record-then-narrow — save the current node as a fallback, then walk toward a tighter one.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(h) time and O(1) space.
Set up a candidate you can improve
Start with ceil = -1. This is both the initial state and the correct answer for the failure case, so no special handling is needed at the end. Point a cursor at the root. Everything from here is a loop that moves the cursor down one level per iteration.
An exact match ends the search immediately
If node.val == x, then x itself is present in the tree. Nothing can be smaller than x while still being ≥ x, so this is provably the tightest possible ceiling. Return it right away — continuing would only waste comparisons.
A node below x forces a right turn
If node.val < x, this node cannot be the ceiling. More importantly, neither can anything in its left subtree, since the BST property puts strictly smaller values there. You discard the node and its entire left side in one comparison, and move the cursor right.
A node above x is recorded, then improved on
If node.val > x, you have found a valid ceiling — but possibly not the smallest one. Save it in ceil, then move left to hunt for something tighter. This is the step people get wrong: it is tempting to return immediately, but a closer value may sit in the left subtree, and the recorded candidate protects you if it does not.
Falling off the tree ends the walk
The loop runs until the cursor becomes null. At that point every node that could have improved the answer has been examined. Return ceil, which holds either the tightest value found or the initial −1 if the tree had nothing at or above x.
Cost is the height, not the node count
Each iteration drops one level, so the work is O(h). On a balanced BST that is O(log n); on a degenerate tree that has collapsed into a chain it is O(n). Space is O(1) with the iterative form — no stack, no output list, just one cursor and one saved value.
Floor is the same walk mirrored
The floor problem — the largest value ≤ x — is this algorithm with both directions flipped: record when node.val < x and move right, go left when the node is too large. Writing both once is the fastest way to stop confusing them in an interview.
Solution & live demo
Common pitfalls
Returning as soon as a valid candidate is found
if root.val > x:
return root.valif root.val > x:
ans = root.val
root = root.leftThe first value above x is a valid upper bound, not the smallest one. In a BST there may be a closer candidate further left, so you record this one and keep narrowing — only when you run out of tree is the saved candidate final.
Going the wrong way after saving the candidate
if root.val > x:
ans = root.val
root = root.rightif root.val > x:
ans = root.val
root = root.leftEverything to the right is even larger, so it can never beat the candidate you just stored. To tighten a ceiling you must look at smaller values — that's the left subtree. (Floor is the exact mirror.)
Edge cases
No candidate ever recorded → −1.
Immediate return of x.