Binary search tree ordering

When to use it

Use it when the tree is a binary search tree and you must find a value, its neighbour in sorted order, or its position in that order.

It belongs to the trees group: Let the shape of the data do the work: the branches of a tree, the letters of a trie, the top of a heap.

Watch it work

Buses leave a stop at set minutes of the hour, and the minutes are kept in a binary search tree. You reach the stop at minute target. Return the minute of the next bus: the smallest minute that is not before yours.

Input
root = [27, 12, 45, 5, 20, 34, 52, null, null, 16]
target = 14

Output
16

root reaches the code as a tree, written here level by level: each node has a value, val, and two children, left and right.

The method

1. Start at the root with no bus kept yet
2. This bus is too early, and so are all on its left: go right
3. Not too early: keep it, then look left for an earlier one
4. The path has ended: return the last bus kept

The run, one moment at a time

1. Step 1. You are at the stop at minute 14. Start at the root, the top node: 27. No bus is kept yet.

   target: 14
   best: empty
   

2. Step 3. Minute 27 is not before 14, so you can catch this bus: keep 27. Everything on its right is later than 27 and cannot be the next bus. Go left.

   target: 14
   best: 27
   

3. Step 2. Minute 12 is before 14: too early. Everything on its left is earlier still, so 5 is ruled out with it. Go right.

   target: 14
   best: 27
   

4. Step 3. Minute 20 is not before 14, and it is earlier than 27: keep 20 in its place. Go left to look for an even earlier bus.

   target: 14
   best: 20
   

5. Step 3. Minute 16 is not before 14, and it is earlier than 20: keep 16 in its place. Go left: there is no node there.

   target: 14
   best: 16
   

6. Step 4. There is no node to go to, so the path has ended. The next bus leaves at minute 16. Only 4 of the 8 nodes were looked at.

   target: 14
   best: 16
   

The code

The numbered comments are the steps of the method.

function solve(root, target) {
  // 1. Start at the root with no bus kept yet
  let node = root;
  let best = null;
  while (node) {
    // 2. This bus is too early, and so are all on its left: go right
    if (node.val < target) {
      node = node.right;
      continue;
    }
    // 3. Not too early: keep it, then look left for an earlier one
    best = node.val;
    node = node.left;
  }
  // 4. The path has ended: return the last bus kept
  return best;
}

def solve(root, target):
    # 1. Start at the root with no bus kept yet
    node = root
    best = None
    while node:
        # 2. This bus is too early, and so are all on its left: go right
        if node.val < target:
            node = node.right
            continue
        # 3. Not too early: keep it, then look left for an earlier one
        best = node.val
        node = node.left
    # 4. The path has ended: return the last bus kept
    return best

How to spot it

Given: The input is a binary search tree

Its ordering lets one comparison rule out a whole side of a node, so most of the tree is never visited.

Asked: In a binary search tree, the smallest value not below a given number

At each node the comparison says whether a better value can only be on the left or only on the right.

Asked: Return a binary search tree's values in sorted order, or its kth smallest

Reading a node's left side, then the node, then its right side meets the values from smallest to largest.

Limits: The tree is balanced and holds a million values

Balanced means no side is much deeper than the other. A path from the top to the bottom is then about 20 nodes, so a search takes about 20 steps.

Looks like it, but is not

• The values are sorted, but they are in an array and not in a tree. Use Binary search on a sorted range. It is the same halving, done with positions: the middle of the range does the job that the root does here.
• The tree has no ordering: a smaller value can be on either side of a node. Use Postorder tree recursion. No comparison can rule out a side then. Every node must be visited, and the answers are combined from below.
• You need the few smallest of many numbers that come in no order. Use Heap of the best k. There is no ordered tree to walk yet. A heap keeps the few best values without putting all of them in order.

Cost and mistakes

Time is one step for each level on the path, written O(h) for a tree of height h. A balanced tree of a million values has about 20 levels; one long chain has a million. Extra space is two variables, O(1).

Watch out

• The rule covers whole sides, not only a node's two children: everything below on the left is smaller than the node, however deep. Comparing each child with its parent is not enough.
• When a node could be the answer, keep it before you move on. The side you go to may hold nothing better, and the walk has no way back up.

In the 150

2 problems of the 150 use it. Naming them gives their method away, so the list is folded.