In-Order Sorted Traversal

Foundations

In the first lesson, each query followed one path and ignored the rest of the tree. Now, what if you need values in order, such as the smallest few or the next larger one, which can sit anywhere in the tree?

An in-order traversal visits a node's left subtree, then the node, then its right subtree. In a BST that order is ascending: everything left of a node is smaller and everything right is larger, so each value comes out after every smaller one. Iteratively, a stack holds the path still to finish: push nodes while going left, pop the next smallest, then move to its right child.

On the balanced tree from nums = [7, 1, 5, 3, 6], push 5, 3, and 1 going left. Pop 1, then 3, then 5; move to 5's right child and push 7, then 6. Pop 6, then 7. The visits come out as 1, 3, 5, 6, 7, sorted without ever sorting, and the walk can stop after any number of pops.

Case Scenario

Kth Smallest Element in a BST asks for the kth value in ascending order, counting from 1. In-order emits values in exactly that order, so count pops and stop at the kth; nothing after it is visited. For root = [5, 3, 6, 2, 4, None, None, 1] and k = 3, the pops are 1, 2, and 3, so the answer is 3.

The direct approach lists every value with a full in-order traversal, then reads index k - 1. It always visits and stores all n values, even when k is 1 and the answer is the leftmost node, which a walk down the left edge reaches in O(h) steps.