BST
Inorder is sorted
Why it matters
Ranked queries appear in leaderboards, ordered indexes, and range-reporting systems. Building a complete sorted list wastes time and memory when the requested rank is near the beginning of a large tree. The kth value must be returned without materializing all n values or completing the traversal beyond the answer.
Example
Kth Smallest Element in a BST
Return the kth smallest value (1-based) in the BST. Inorder traversal of a BST is sorted.
- Input
- root = [5, 3, 6, 2, 4, None, None, 1], k = 3
- Output
- 3
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Kth Smallest Element in a BST
root = [5, 3, 6, 2, 4, None, None, 1], k = 3→3
The baseline, List every value, then index, is O(n) · O(n). The better model below keeps this exact input and removes that bottleneck.
For [5, 3, 6, 2, 4, None, None, 1] and k = 3, the brute list stores [1, 2, 3, 4, 5, 6]. A lazy inorder walk emits only 1, 2, and 3, then stops before expanding the remaining work for 4, 5, and 6.
For [5, 3, 6, 2, 4, None, None, 1] with k = 3, push 5, 3, 2, and 1 while following left children. Pop 1 first; with no right child, pop 2 second.
Pop 3 third, decrementing k to 0, and return 3 immediately. If another value were needed, the walk would enter 3's right subtree at 4 before returning to 5. The stack holds only the unfinished root-to-current path.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.