Kth smallest element in a BST

An inorder walk visits BST keys in sorted order, so stop as soon as the kth one is seen.

The idea

Inorder traversal of a BST (left, node, right) produces keys in ascending order. Using an explicit stack instead of recursion, push every node while walking left, then pop one at a time; each pop is the next smallest key not yet seen. Count pops, and the moment the count reaches k, that popped node holds the answer, with no need to keep going.

Code

public static int KthSmallest(TreeNode root, int k) {
    var stack = new Stack<TreeNode>();
    TreeNode node = root;
    while (node != null || stack.Count > 0) {
        while (node != null) { stack.Push(node); node = node.left; }
        node = stack.Pop();
        if (--k == 0) return node.val;
        node = node.right;
    }
    return -1;
}

Tips

• Because the walk stops at k, this costs O(h + k) rather than a full O(n) inorder traversal followed by indexing.

In the .NET library

Augmenting each node with the size of its subtree turns this into an O(h) lookup with no traversal at all, the trick behind an order-statistics tree.