Pattern visualizer

Kth Largest Element in a BST

Reverse inorder (right, node, left) is the mirror image of the standard traversal: instead of ascending order it visits every key in strictly descending order. So the kth largest 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 right 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 largest value in the BST (1-indexed). Expected: 4..

Early-stopping reverse-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 kthLargest(root, k=3). Point node at the root, 5, with an empty stack. A BST's REVERSE inorder traversal (right, node, left) visits keys in strictly descending order, so the kth key it emits is the kth largest — 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.right
7  node <- POP(stack)
8  k <- k - 1
9  IF k = 0:
10    RETURN node.val
11  node <- node.left

← / → step · space play · Home restart

Where to practice BST

Practice BST problems All BST problems Back to roadmap