AlgoScope

BST Queries

algorithmintermediateTime O(h)Space O(1)

Smaller left, larger right is one rule, but it answers many questions. The smallest is all the way left. The next value up is the last place you turned left. A range only needs the subtrees that could hold it.

2030354050607080

Find the smallest value. Keep going left until you cannot, and that node is it.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. At 50. Is this the smallest, or is there more to the left?

    • Go left
    • Go right
    • Stop here

    Answer: Go left. A left child means at least one smallest value is still down there.

  2. At 30. Is this the smallest, or is there more to the left?

    • Go left
    • Go right
    • Stop here

    Answer: Go left. A left child means at least one smallest value is still down there.

  3. At 20. Is this the smallest, or is there more to the left?

    • Go left
    • Go right
    • Stop here

    Answer: Stop here. No left child means no smallest value exists below.

How it runs, step by step

  1. Find the smallest value. Keep going left until you cannot, and that node is it.

    Finding the smallest value by walking left from the root until there is no left child.

  2. 50 has a left child, so something smallest is still below. Keep going.

    At 50. Moving left.

  3. 30 has a left child, so something smallest is still below. Keep going.

    At 30. Moving left.

  4. 20 has no left child, so nothing smallest remains. This is it.

    At 20. No left child, so this is the smallest.

  5. The smallest value is 20, found in 3 steps. That is the height of one side, never the whole tree.

    The smallest value is 20.

Remember

  • Every query here is O(height), which is O(log n) while the tree stays balanced.
  • The successor is the last node you turned left at, unless the right subtree has a minimum.
  • A range search skips any subtree the ordering rules out, which is what makes it fast.

Topics covered

Related

Where this is used

Standard librariesOrdered maps in standard libraries

Java's TreeMap and C++'s std::map are balanced search trees, and their API is this lesson's operation list under other names: firstKey and lastKey are min and max, higherKey and ceilingKey are the successor walk, subMap in Java and lower_bound with upper_bound in C++ are the range query. A hash map can answer none of them, because hashing deliberately destroys the ordering these walks depend on. That one difference is why both languages ship an ordered map next to the hash one instead of picking a winner.

DatabasesIndex range scans

An index on a column is a search tree over that column, so a query asking for timestamps between two bounds descends once to the lower bound and then walks forward, touching only rows it will return. MIN and MAX on an indexed column are the same move: PostgreSQL rewrites those aggregates into a walk to the leftmost or rightmost leaf rather than a scan of the table. When a planner picks an index scan over a sequential scan, these O(h) descents are what it is picking.

Operating systemsPicking the next task to run

Linux's CFS scheduler kept every runnable task in a red-black tree keyed by virtual runtime and always ran the leftmost node, which is the minimum query, executed on every context switch. Because that query is among the hottest paths in the kernel, the run queue also cached a pointer to the leftmost node so the walk could be skipped entirely and only refreshed when that node left the tree. It is a good demonstration that min stays cheap even when the tree is being rewritten constantly.

Developer toolsgit merge-base

A three-way merge needs the lowest common ancestor of the two branch tips to diff against, which is what git merge-base computes. Git history is a directed acyclic graph rather than a search tree, so it has to actually search, and merges turn ambiguous when several candidate ancestors tie. The contrast is the lesson: the BST version is a single walk down only because the keys already tell you which side each node is on.

Why it works this way

Why the successor loop needs no special case for the right subtree

The textbook version has two cases: if the node has a right subtree, take that subtree's minimum, otherwise climb back up to the lowest ancestor whose left subtree holds the node, which is the last ancestor you turned left at on the way down. The single loop here covers both because it never stops when it finds the key. On reaching the node that holds the key it turns right, and from there every key is larger, so it keeps turning left and lands on exactly that subtree's minimum. That is also why it needs no parent pointers, which the climbing version cannot do without.

Why the first split is the lowest common ancestor

While both keys fall on the same side of the current node, you are still above both of them, so you have not gone too far. The first node where they fall on opposite sides, or where one of them equals the node, is the last node shared by both root-to-node paths, which is the definition of the lowest common ancestor. The order of the two arguments does not matter, because each test checks both keys against the current node. The loop does assume both keys are in the tree: give it two absent values and it returns the point where they would have split, or walks off the bottom and trips whichever non-null assertion it reaches, c.left going down the left edge or c.right going down the right one.

Out of range means prune one side, not stop

A range search that returns as soon as a node's key falls outside low..high throws away everything beneath it. A node holding 10 with a range of 35 to 65 is itself out of range, but its right subtree is exactly where the answers live. The rule is per side, not per node: skip the left child only when the key is already at or below low, skip the right child only when it is at or above high.

The O(1) space covers the walks, not the range query

Min, max, successor and lowest common ancestor are loops that only ever move downward, so they hold a pointer or two and nothing more. A range search has to descend into two children from the nodes that straddle the bounds, so it needs recursion or an explicit stack, which is O(h). Its time is O(h + k) for k matches rather than O(h), because reporting k values cannot take fewer than k steps no matter how good the pruning is.

Read more

Next up