Kth Largest Element in BST

Given the root of a binary search tree and an integer k (1 <= k <= number of nodes), return the k-th largest value in the BST.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

A reverse inorder (right, node, left) visits a BST in descending order.

So the k-th largest is the k-th node of a reverse inorder walk.

Use an iterative reverse inorder and stop after k pops.

Common doubts

Visiting the right subtree (all larger) before the node before the left subtree (all smaller) yields values largest-first.

It's the exact mirror — swap every left/right in the kth-smallest solution.

For small k you only need the first k largest values, not a full sort.

Interview follow-ups

· What an interviewer asks next.

Augment nodes with subtree sizes and descend using the counts — O(log n) per query on a balanced tree.

Yes — one ascending inorder gives index k-1 (smallest) and index n-k (largest).

Fun facts

kth-largest and kth-smallest are the same algorithm reflected — the BST's symmetry made visible.
The descending walk here is a right-leaning version of the BST iterator's mechanism.

Asked at

AmazonFlipkartMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: root = [5, 3, 6, 2, 4], k = 2
Output: 5
Descending order is 6, 5, 4, 3, 2; the 2nd largest is 5.

Example 2

Input: root = [5, 3, 6, 2, 4], k = 1
Output: 6
The largest value.

Constraints

- The number of nodes n is in the range [1, 10^4] - 1 <= k <= n - 1 <= Node.val <= 10^4 - root is a valid BST

If an inorder traversal of a BST is ascending, a reverse inorder (right, node, left) is descending — so the k-th largest is the k-th node of a reverse inorder walk. And you can stop after k pops instead of sorting everything.

Prerequisites

Before you start

· Concepts used directly in the solution.

Reverse inorder = descending. right, node, left visits a BST largest-first.

Iterative traversal. A stack walk you can stop early.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Is k 1-indexed?”

Yes — k = 1 is the largest value.

“Is k always valid?”

Yes — 1 <= k <= number of nodes.

The ideal opening — say it like this

Reverse inorder visits a BST in descending order, so the k-th largest is the k-th node I visit that way.

I use an iterative reverse-inorder and stop as soon as I've popped k nodes.

Understand the problem

Worked example — BST [5, 3, 6, 2, 4], k = 2

reverse inorder (descending): 6, 5, 4, 3, 2
2nd largest = 5

Key observations

1Aha

Reverse inorder is descending

Swapping the left/right visit order turns ascending into descending.

2Aha

Stop after k pops

No need to traverse the whole tree for a small k.

3Aha

Mirror of kth-smallest

Identical structure with left and right swapped.

Brute force vs optimal

	Full inorder, index from end	Reverse inorder, stop at k
Idea	Sort via inorder, take n-k	Descend right-first, stop at k
Time	O(n)	O(height + k)
Space	O(n)	O(height)

Both use the ordering; the reverse walk stops early. Full code is in the Approaches selector below.

Summary

Key takeaway

Reverse inorder (right, node, left) visits a BST descending, so the k-th largest is its k-th node. Stop after k pops — O(height + k).

reverse-inorder pop the next-largest; k -= 1
if k == 0: return that node's value