Pattern visualizer

Find Kth Smallest and Largest in BST

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

Two early-stopping traversals sharing one routine

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

Call stack

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

line 1

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

Where to practice BST

Practice BST problems All BST problems Back to roadmap