Floor in BST
Largest BST value ≤ x (the floor), or −1 if none.
- 1 <= number of nodes <= 10⁵
- 1 <= node value, x <= 10⁹
- Return -1 when no value is <= x
Intuition
The floor in BST is the largest value less than or equal to x. Collecting all the values and scanning would work, but it discards the structure the tree is handing you: at every node, one comparison tells you which entire half of the remaining tree is worth exploring.
Stand at a node with value v. If v > x, then v is too large to be a floor — and so is everything in its right subtree, since a BST keeps larger values on the right. That one comparison eliminates a node and an entire subtree, and the search continues left.
If v <= x, then v qualifies as a floor. But it may not be the largest qualifying value, because the right subtree could hold something between v and x. So you do two things at once:
- Record v as the best answer so far, then move right anyway to try to beat it.
The walk goes straight down with no backtracking, and the saved candidate only improves. If you fall off the bottom having recorded nothing, every value in the tree exceeded x, and the answer is −1. This is the exact mirror of the ceiling problem, which records on the other comparison and turns the other way.
The mirror of ceil: the largest value not exceeding x. Same record-then-narrow skeleton, with both comparisons flipped. Recognising that these two problems are one problem with a sign change is worth more than memorising either — the same idea gives you inorder-successor and predecessor for free.
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.
Initialise the answer to the failure value
Start with floor = -1, which is both the starting state and the correct output when no value qualifies. Point a cursor at the root; the loop moves it down one level per iteration.
Stop immediately on an exact match
If node.val == x, then x is present in the tree. Nothing can be larger than x while still being ≤ x, so this is provably the tightest floor. Return it right away rather than continuing the descent.
Record and go right when the node fits
If node.val < x, this node is a valid floor. Save it, then move right — the right subtree holds larger values, which may still be ≤ x and therefore closer. This is the step to get right: returning early would miss a tighter answer.
Go left when the node is too large
If node.val > x, this node cannot be the floor, and neither can anything in its right subtree, since those values are larger still. Move left, discarding a node and a subtree in one comparison.
Return whatever survived the walk
When the cursor falls off the tree, every node that could have improved the answer has been seen. Return floor — either the tightest value found or the initial −1.
Cost and the mirror relationship
One step per level gives O(h) time and O(1) space with the iterative form. The ceiling problem is this same walk with both the comparison and the turn direction flipped; writing them side by side once is the fastest way to stop mixing them up under interview pressure.
Solution & live demo
Common pitfalls
Copying the ceil solution without flipping both halves
if root.val < x:
ans = root.val
root = root.leftif root.val < x:
ans = root.val
root = root.rightTwo things flip between floor and ceil — which comparison stores a candidate, and which direction tightens it. Flipping only the comparison and keeping ceil's direction walks away from every better answer, so you return the first value below x rather than the largest.
Seeding the answer with a real value
ans = root.val
ans = -1
When every node exceeds x there is no floor, and the problem expects -1. Seeding from the root reports a value that is larger than x, which is not a floor at all.
Edge cases
No node qualifies; return −1 (or None).
Early exit with x itself.