Order Traversal

What is this?

Both problems here are the same walk pointed in opposite directions. Go left, node, right and a BST hands you its values in ascending order — so the k-th value arrives on the k-th step and you can stop. Go right, node, left and they arrive descending — so a single running total, accumulated as you go, already holds the sum of everything larger by the time you reach each node.

No sorting, no second pass, no auxiliary array. The traversal order is the algorithm.

💡 Fun fact: Convert BST to Greater Tree looks like it needs two passes — first learn every value, then compute each node's suffix sum. Reverse inorder collapses it to one, because visiting largest-first means the accumulator has already seen exactly the values that should be added to the current node at the moment you arrive. The traversal order does the work that a second pass would otherwise have to.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: choose the traversal direction that makes the values arrive in the order the problem needs, then either stop early or accumulate as you go — both turn what looks like two passes into one.

1. Early exit needs an iterative walk

Recursion cannot easily abandon a traversal midway. An explicit stack can:

def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:                 # dive as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()          # this is the next value in sorted order
        k -= 1
        if k == 0:
            return node.val         # stop — everything to the right is untouched
        node = node.right
    return -1

The cost is O(h + k): h to descend to the smallest value, then k steps. For k = 1 on a balanced tree that is a handful of nodes out of a million — and it is why "flatten the whole tree into a list, then index" is the answer to avoid, even though it is correct.

The classic follow-up is what if the tree is modified frequently and k-th queries are common? The answer is to augment each node with the size of its left subtree, making each query a genuine O(h) descent. Volunteer it.

2. Accumulate in reverse

running = 0

def reverse_inorder(node):
    global running
    if not node: return
    reverse_inorder(node.right)     # everything larger, first
    running += node.val
    node.val = running              # the sum of all values >= the original
    reverse_inorder(node.left)

The order of those three statements is the entire problem. Visit right first, then update, then go left — and each node is rewritten exactly when the accumulator holds the correct total.

3. A 30-second worked example

        4
       / \
      1   6
       \    \
        2    7

reverse inorder visits: 7, 6, 4, 2, 1

node 7 → running = 7   → becomes 7
node 6 → running = 13  → becomes 13
node 4 → running = 17  → becomes 17
node 2 → running = 19  → becomes 19
node 1 → running = 20  → becomes 20

Check node 4: values greater than or equal to it are 4, 6, 7 = 17 ✓. Every node got its answer at the instant it was visited, with no lookahead.

4. Where you'll actually meet this

• Leaderboards. "k-th highest score" with an early exit, and subtree-size augmentation when the data changes constantly.
• Financial reporting. Suffix totals — "revenue from all accounts at or above this tier" — are the reverse-inorder accumulation.
• Database query planners. ORDER BY … LIMIT k over an index is exactly early-stopping inorder; the engine stops reading once k rows are produced.
• Percentile and quantile queries. Rank-based lookups over an order-statistic tree use the augmented-size variant.
• Analytics dashboards. Running cumulative totals over a sorted dimension are one directional pass.

5. Problems in this chapter

▶ Kth Smallest Element in a BST

Return the k-th smallest value. Iterative inorder with a counter, stopping the moment k reaches zero.
Pattern: early-stopping inorder. Target: O(h + k) time, O(h) space.

▶ Convert BST to Greater Tree

Replace each value with the sum of all values greater than or equal to it. Reverse inorder with a running accumulator.
Pattern: reverse-inorder accumulation. Target: O(n) time, O(h) space.

6. Common pitfalls 🚫

• Flattening to a sorted list first. Correct, O(n) time and space, and it discards the entire point of the structure.
• Recursing without a way to stop. Recursion makes the early exit awkward; use an explicit stack, or a sentinel that short-circuits every remaining call.
• Updating before recursing right. In the accumulation problem the order right → update → left is mandatory; any other order gives wrong sums.
• Using a local accumulator. It must persist across the whole traversal — an instance attribute, a nonlocal, or a single-element list.
• Off-by-one on k. Decrement then test for zero; testing before decrementing returns the (k+1)-th value.
• Assuming h = log n. A degenerate BST makes every one of these O(n).
• Missing the follow-up. "What if the tree changes often?" has a real answer — augment with subtree sizes — and interviewers are usually waiting for it.

7. Key takeaways

1. Inorder ascends, reverse inorder descends. Pick the direction and most of the work disappears.
2. Stop as soon as the answer exists. O(h + k) beats O(n) by orders of magnitude for small k.
3. An iterative walk is what makes early exit natural.
4. Accumulate during the traversal rather than gathering values and post-processing.
5. Statement order is the algorithm in the reverse walk — right, update, left.
6. Augment with subtree sizes when queries are frequent and the tree mutates.
7. Why interviewers like it: the sorted-list solution is instantly available, so choosing not to use it is the signal.

Order: Kth Smallest Element in a BST → Convert BST to Greater Tree.

The pruning reflex both of these rest on — compare, descend, and discard half the tree — is drilled by the O(h) inorder-successor walk in 101.