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 next value after 40. Walk down, and every time you turn left, the node you just left is a candidate: it beats 40, and so does everything to its right.

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, looking for the next value after 40. Which way?

    • Go left
    • Go right
    • Stop here

    Answer: Go left. 50 > 40, so it is a candidate, and anything better must be to its left.

  2. At 30, looking for the next value after 40. Which way?

    • Go left
    • Go right
    • Stop here

    Answer: Go right. 30 <= 40, so the answer, if any, is to the right.

  3. At 40, looking for the next value after 40. Which way?

    • Go left
    • Go right
    • Stop here

    Answer: Go right. 40 <= 40, so the answer, if any, is to the right.

How it runs, step by step

  1. Find the next value after 40. Walk down, and every time you turn left, the node you just left is a candidate: it beats 40, and so does everything to its right.

    Finding the successor of 40. Each left turn records a candidate.

  2. 50 beats 40, so it is a candidate. Go left to look for something smaller that still beats 40.

    At 50. It beats 40, so it is remembered and the walk turns left.

  3. 30 is not bigger than 40, so it cannot be the answer. Go right.

    At 30. It does not beat 40, so the walk turns right.

  4. 40 is not bigger than 40, so it cannot be the answer. Go right.

    At 40. It does not beat 40, so the walk turns right.

  5. The successor of 40 is 50, the last candidate recorded. 3 steps.

    The successor of 40 is 50.

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