Inorder = sorted order

34 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A binary search tree: 5 at the top; 3 and 6 below; 2 and 4 under 3; 1 under 2. What is the third smallest value? By hand you might collect all the values, sort them, and read the third: 1, 2, 3, 4, 5, 6, so 3. Sorting n numbers costs about n log n, and it ignores the fact that the tree is already arranged by size. A BST stores its values in sorted order; it is just hidden in the shape.

Build the structure, one piece at a time

Piece one: the inorder walk. At any node, first walk the whole left subtree, then look at the node itself, then walk the right subtree. In a BST everything on the left is smaller and everything on the right is larger, so this walk visits the values in increasing order with no sorting at all. Try it: left from 5 to 3, left to 2, left to 1; 1 has no left, visit 1; 1 has no right; back to 2, visit 2; back to 3, visit 3; then 4, then 5, then 6.

Piece two: a counter, or more generally a memory of the previous visited value. Each visit is one event in sorted order, so a counter that increments on each visit tells you the rank of the value you are looking at. Stop when it reaches k.

Piece three: variations of the memory. Keep the previous value and the current one, and you get the smallest gap between any two values (they must be neighbours in sorted order). Keep the previous value and a run length, and you get the most frequent value. Keep the previous value and check it is smaller than the current, and you have validated the BST. Collect the values into a list and run two pointers from both ends, and you have two-sum in a BST.

Why it is correct

The claim: inorder on a BST visits values in increasing order. Argue by the structure of the tree. For a node v, every value in its left subtree is less than v, and all of those are visited before v; every value in its right subtree is greater and visited after. Apply the same statement inside each subtree. Any two values are then visited in the correct order: either one is an ancestor of the other, handled by the rule above, or they sit in different subtrees of some common ancestor, where the left one is smaller and visited first.

the k-th node visited by inorder = the k-th smallest value

So the counter reading k at a visit identifies exactly the k-th smallest, and "previous < current at every visit" is equivalent to the whole tree being a BST.

Why it is fast

A full walk touches every node once: O(n), with no sorting. For the k-th smallest you walk down the left spine (h steps) and then do k visits, O(h + k). The memory is just the recursion stack or an explicit stack, O(h), plus one or two remembered values. Compared with collecting and sorting, this is both faster and needs no extra array.

How to recognise it in an interview

Any question on a BST that mentions order: "kth smallest", "smallest difference between any two nodes", "the mode", "two nodes were swapped, fix the tree", "convert to a sorted list". Say: "Inorder on a BST is sorted order, so I will walk inorder and keep whatever running state the question needs." Kth Smallest Element in a BST keeps a counter and stops early. Minimum Absolute Difference in BST keeps the previous value and the smallest gap seen. Recover Binary Search Tree keeps the previous value and notes the one or two places where the order drops, which are the swapped nodes.

02The idea in one line

An inorder walk visits keys ascending; remember the previous key.

Reach for it when: kth smallest, min absolute diff, mode, recover swapped nodes, two sum in BST.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Kth smallest (k=3) in [5,3,6,2,4,null,null,1]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Go left as deep as possible: the smallest key is at the leftmost node
2. At 5: left subtree first
3. At 3: left subtree first
4. At 2: left subtree first
5. At 1: no left child, so it is next in order
6. Visit 1: count = 1
7. Visit 2: count = 2
8. Visit 3: count = 3
9. count = k: the 3rd smallest is 3, stop early
10. Stopped after k visits: O(h + k)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search Tree: BST range bounds, BST insert / delete / search, Build a balanced BST from sorted input.