Find the K-th Largest Value in a Search Tree
Solve this ProblemYou are given the root of a binary search tree with distinct values and an integer k. Return the k-th largest value in the tree, where k = 1 means the largest. If the tree has fewer than k values, return -1.
Visiting the tree right subtree first, then the node, then the left subtree produces the values from largest to smallest — so the k-th largest is the k-th value visited, and the walk can stop there.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ◆
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ◆
1 ≤ k ≤ 150 (k may be larger than the number of nodes) - ◆
Return the k-th largest value in the tree (k = 1 is the largest). If the tree has fewer than k values, return -1
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Write Out the Whole Sorted List, Count From the End
BruteAn inorder walk gives the values in ascending order. Collect them all; then the k-th largest is the item k places from the END, at index (length − k) — or -1 if that index would be negative because the tree has fewer than k values. It always walks the whole tree and stores every value: O(n) time and O(n) space.
O(n)O(n)1class Solution {
2 public int kthLargest(TreeNode root, int k) {
3 List<Integer> vals = new ArrayList<>();
4 inorder(root, vals);
5 int index = vals.size() - k;
6 return index >= 0 ? vals.get(index) : -1;
7 }
8
9 private void inorder(TreeNode node, List<Integer> vals) {
10 if (node == null) return;
11 inorder(node.left, vals);
12 vals.add(node.val);
13 inorder(node.right, vals);
14 }
15}Optimal — Reverse Inorder (Right, Node, Left) That Stops at the K-th Visit
OptimalMirror the inorder walk: visit the RIGHT subtree first, then the node, then the LEFT subtree — this produces the values in DESCENDING order. Use an explicit stack: from the current node keep going right, pushing nodes; pop one (the next largest value), count it, and continue with its left child. The k-th value popped is the k-th largest, so stop right there. Only the rightmost path and the nodes up to the k-th value are handled: O(h + k) time, at most h nodes on the stack, and no list.
O(h + k)O(h)1class Solution {
2 public int kthLargest(TreeNode root, int k) {
3 Deque<TreeNode> stack = new ArrayDeque<>();
4 TreeNode cur = root;
5 int count = 0;
6 while (cur != null || !stack.isEmpty()) {
7 while (cur != null) {
8 stack.push(cur);
9 cur = cur.right;
10 }
11 cur = stack.pop();
12 count++;
13 if (count == k) return cur.val;
14 cur = cur.left;
15 }
16 return -1;
17 }
18}