BST Patterns

Kth Smallest

In-order traversal visits BST nodes in sorted order. So just do an in-order traversal and count — when you reach the Kth node, that's your answer. Can stop early without visiting all nodes.

O(h + k)

O(h)

How It Works

Kth smallest in a BST exploits the fact that in-order traversal emits BST values in ascending order. Run left-root-right while decrementing a counter at each visit; when the counter hits zero, the current node is the answer and the traversal aborts. No sorting, no extracting values into an array — the tree's structure already is the sorted order.

Early termination is the efficiency point: the traversal descends at most h levels before reaching the smallest element, then visits k nodes, giving O(h + k) time and O(h) stack space instead of a full O(n) sweep. If the tree is queried repeatedly and modified, augmenting each node with its left-subtree size upgrades queries to O(h): at each node compare k against leftCount + 1 and descend left, stop, or descend right with k reduced accordingly.

Step-by-Step Visualization

Find 3rd smallest in BST. In-order gives sorted

In-order[2, ...]

1/3

Code

Java

static int kthSmallest(TreeNode root, int k) {
  Stack<TreeNode> stack = new Stack<>();
  TreeNode curr = root;

  while (curr != null || !stack.isEmpty()) {
    while (curr != null) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    k--;
    if (k == 0) return curr.val;
    curr = curr.right;
  }
  return -1;
}

Tips & Gotchas

1In-order traversal of BST visits nodes in sorted order

2Count nodes visited; stop at the kth one

3Can augment BST nodes with subtree sizes for O(h) lookup

Practice Problems

1Kth Smallest Element in a BST
2Second Minimum Node in a Binary Tree
3Inorder Successor in BST
4Binary Search Tree Iterator

About the BST Patterns Pattern

Binary Search Trees guarantee: everything in the left subtree < root < everything in the right subtree. This property lets you make decisions at each node about which direction to go, effectively doing binary search on a tree.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

How do I make kth-smallest fast when the BST changes between queries?

Store in each node the count of nodes in its left subtree, updating counts on insert and delete. A query then navigates like binary search: if k equals leftCount + 1 you are at the answer, if smaller go left, otherwise go right with k minus leftCount minus 1. Each query becomes O(h).

Why not just collect all values into a sorted array first?

It works but costs O(n) time and O(n) extra space on every query, and the array goes stale when the tree mutates. The early-exit in-order traversal answers in O(h + k) with only stack space, which is a significant win when k is small relative to n.