Kth Smallest Element in a BST

Early-stopping inorder traversal with an explicit stack

time O(h + k)space O(h)

An inorder traversal of a BST (left, node, right) visits every key in strictly ascending order — that is the ordering invariant paying off directly. So the kth smallest element is simply the kth value that traversal emits, and there is no need to collect all n values first: an explicit stack can walk left as far as possible, pop one node at a time, count down k, and return the instant k reaches zero — skipping every node past the answer.

Details

Animated on: root = [5,3,6,2,4,null,null,1], k = 3 — return the kth smallest value in the BST (1-indexed). Expected: 3.

Problem:Kth Smallest Element in a BSTMedium

Pattern:Binary Search Tree Problems

Early-stopping inorder traversal with an explicit stack

step 1 / 14

Call stack

k = 3stack: []node → 5

Call kthSmallest(root, k=3). Point node at the root, 5, with an empty stack. A BST's inorder traversal (left, node, right) visits keys in strictly ascending order, so the kth key it emits is the answer — no sorting needed.

Pseudocode

1node <- root
2stack <- EMPTY
3WHILE node != null OR stack NOT EMPTY:
4  WHILE node != null:
5    PUSH node TO stack
6    node <- node.left
7  node <- POP(stack)
8  k <- k - 1
9  IF k = 0:
10    RETURN node.val
11  node <- node.right

← / → step · space play · Home restart

Every step in words

Show all 14 steps

Call kthSmallest(root, k=3). Point node at the root, 5, with an empty stack. A BST's inorder traversal (left, node, right) visits keys in strictly ascending order, so the kth key it emits is the answer — no sorting needed.
5 has a left child, so push it onto the stack and descend: node ← node.left = 3.
3 has a left child, so push it onto the stack and descend: node ← node.left = 2.
2 has a left child, so push it onto the stack and descend: node ← node.left = 1.
1 has no left child. Push it too — the inner loop now stops with node null. The stack (bottom to top: 5, 3, 2, 1) is exactly the unvisited path down to the smallest key seen so far.
Inner loop is done (node was null). Pop the stack: node ← 1 — the next key in ascending order.
k ← k - 1 = 2. Not zero yet — 1 is not the answer.
2's right child is null, so node ← null; the outer loop will pop the stack again next.
Inner loop is done (node was null). Pop the stack: node ← 2 — the next key in ascending order.
k ← k - 1 = 1. Not zero yet — 2 is not the answer.
3's right child is null, so node ← null; the outer loop will pop the stack again next.
Inner loop is done (node was null). Pop the stack: node ← 3 — the next key in ascending order.
This is the 4th node visited in order — k ← k - 1 = 0, the countdown lands exactly on 3.
k = 0, so return node.val = 3 right away. The traversal never touches 4, 5 or 6 — stopping the instant k hits zero is what keeps this O(h + k) instead of the O(n) it costs to build the full sorted list.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Kth Smallest Element in a BST in the editor All BST problems Back to roadmap