k-th Smallest in BST

Two early-stopping traversals sharing one routine

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

A BST's inorder traversal (left, node, right) visits keys in ascending order, and its mirror — reverse inorder (right, node, left) — visits them in descending order. So the kth smallest and kth largest are found by the exact same early-stopping stack routine run twice: once descending NEXT = left first (ascending, for the smallest), once descending NEXT = right first (descending, for the largest). Each run stops the instant its own count reaches k, so together they touch far fewer nodes than collecting every value into an array.

Details

Animated on: root = [5,3,6,2,4,null,null,1], k = 2 — return both the kth smallest and kth largest values in the BST. Expected: [2, 5].

Problem:k-th Smallest in BSTMedium

Two early-stopping traversals sharing one routine

step 1 / 9

Call stack

k = 2phase: kth smallest (left-first)

Call kthSmallestAndLargest(root, k=2). The plan: run the same early-stopping stack traversal twice — left-first (normal inorder) to find the kth smallest, then right-first (reverse inorder) to find the kth largest — stopping each the instant its count hits k.

Pseudocode

1stack <- EMPTY, node <- root
2WHILE node != null:
3  PUSH node TO stack
4  node <- NEXT(node)
5count <- 0
6WHILE stack NOT EMPTY:
7  node <- POP(stack)
8  count <- count + 1
9  IF count = k:
10    RETURN node.val
11  node <- OTHER(node)
12  WHILE node != null:
13    PUSH node TO stack
14    node <- NEXT(node)

← / → step · space play · Home restart

Every step in words

Show all 9 steps

Call kthSmallestAndLargest(root, k=2). The plan: run the same early-stopping stack traversal twice — left-first (normal inorder) to find the kth smallest, then right-first (reverse inorder) to find the kth largest — stopping each the instant its count hits k.
Descend left as far as possible: 5 → 3 → 2 → 1. The leftmost node visited holds the smallest key remaining in the tree.
Pop 1 — count=1, not k=2 yet. 1 has no right subtree, so back up the stack for the next visit.
Pop 2 — count=2 matches k=2, so 2 is the kth smallest. Stop this traversal immediately; the other subtree(s) are never visited.
Kth smallest found: 2. Restart the same routine from the root, this time right-first, for the kth largest.
Descend right as far as possible: 5 → 6. The rightmost node visited holds the largest key remaining in the tree.
Pop 6 — count=1, not k=2 yet. 6 has no left subtree, so back up the stack for the next visit.
Pop 5 — count=2 matches k=2, so 5 is the kth largest. Stop this traversal immediately; the other subtree(s) are never visited.
Both traversals are done: kth smallest = 2, kth largest = 5. Return the pair [2, 5].

Now solve it yourself

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

Solve k-th Smallest in BST in the editor All BST problems Back to roadmap