Floor in a BST

Floor in a BST asks for the largest value in a binary search tree that does not exceed a given key. It is a clean exercise in using the BST ordering to steer a single walk from the root, never touching more than one branch per level.

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

The slow way first

The obvious idea: collect every value in the tree, throw out the ones bigger than key, and take the max of what remains. That works, but it visits all n nodes and ignores the structure entirely — it would give the same answer on an unsorted pile of numbers.

The question to ask: the tree is sorted, so why am I looking at every node? The BST invariant — everything in the left subtree is smaller, everything in the right subtree is larger — lets us discard half the tree at each step.

The idea: go right on a candidate, left when too big

Walk down from the root with one rule per node:

• If node.val <= key, this node is a valid floor candidate, so record it. Any value that is still <= key but larger must be to the right, so go right to try to do better.
• If node.val > key, this node is too big to ever be the floor, so go left toward smaller values.

The last candidate we recorded before falling off the tree is the answer.

Because each step moves to exactly one child, we touch at most one node per level — an O(h) walk, where h is the height of the tree.

Walk through it

Step through the animation with key = 11. We start at 8 (8 <= 11, record it, go right), hit 12 (12 > 11, too big, go left), reach 10 (10 <= 11, a better candidate, record it, go right), and then run off the bottom because 10 has no right child. The last recorded candidate, 10, is the floor.

Pseudocode

floor = None
node = root
while node is not None:
    if node.val == key:        # exact match is its own floor
        return node.val
    if node.val < key:         # candidate; a bigger one may be to the right
        floor = node.val
        node = node.right
    else:                      # too big; smaller values are to the left
        node = node.left
return floor

The Python solution

def floor_in_bst(root, key):
    floor = None
    node = root
    while node is not None:
        if node.val == key:
            return node.val
        if node.val < key:
            floor = node.val
            node = node.right
        else:
            node = node.left
    return floor

• floor holds the best candidate found so far; it starts as None.
• We loop with node, stepping toward one child each iteration until we fall off the tree.
• An exact match (node.val == key) is trivially the floor, so we return immediately.
• When node.val < key, the node qualifies — we update floor and go right to look for a larger qualifier.
• When node.val > key, we skip it and go left, because everything to the right is even bigger.
• Falling off the tree (node is None) ends the loop, and we return the last recorded floor.

Complexity

For a balanced tree h is O(log n), so the walk is logarithmic; for a degenerate (chain-like) tree it can be O(n). Either way we use only O(1) extra space — just two variables.

When this pattern shows up

Practice