Skip to main content
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)
say this out loud

In-order on a BST yields sorted values, so I count as I go and stop at k rather than materialising the whole traversal.

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 the 3rd smallest in a BST with 5 at the root, 3 and 6 below, and 2 and 4 under the 3
5
0
3
1
6
2
2
3
4
4
k3
1/8

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.