Pattern visualizer

Kth Smallest Element in a BST

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. 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..

Early-stopping inorder traversal with an explicit stack

time O(h + k)space O(h)step 1 / 14

Call stack

k = 3stack: []node → 5

line 1

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

Where to practice BST

Practice BST problems All BST problems Back to roadmap