Kth Largest Element in a BST

Early-stopping reverse-inorder traversal with an explicit stack

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

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.

Details

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.

Problem:Kth Largest in BSTEasy

Early-stopping reverse-inorder traversal with an explicit stack

step 1 / 14

Call stack

k = 3stack: []node → 5

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

Every step in words

Show all 14 steps

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.
5 has a right child, so push it onto the stack and descend: node ← node.right = 6.
6 has no right child. Push it too — the inner loop now stops with node null. The stack (bottom to top: 5, 6) is exactly the unvisited path down to the largest key seen so far.
Inner loop is done (node was null). Pop the stack: node ← 6 — the next key in descending order.
k ← k - 1 = 2. Not zero yet — 6 is not the answer.
5's left 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 ← 5 — the next key in descending order.
k ← k - 1 = 1. Not zero yet — 5 is not the answer.
Descend into the left subtree: node ← node.left = 3.
3 has a right child, so push it onto the stack and descend: node ← node.right = 4.
4 has no right child. Push it too — the inner loop now stops with node null. The stack (bottom to top: 3, 4) is exactly the unvisited path down to the largest key seen so far.
Inner loop is done (node was null). Pop the stack: node ← 4 — the next key in descending order.
This is the 4th node visited in descending order — k ← k - 1 = 0, the countdown lands exactly on 4.
k = 0, so return node.val = 4 right away. The traversal never touches 3, 2 or 1 — 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 Largest in BST in the editor All BST problems Back to roadmap