5.34 Find the k-th Largest Node in a BST

5.34.1 Problem Metadata

5.34.2 Description

Given the root of a Binary Search Tree (BST) and an integer k, return the k-th largest value in the BST.

5.34.3 Examples

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 4
Explanation: Values in descending order: 6, 5, 4, 3, 2, 1. The 3rd largest is 4.

       5
      / \
     3   6
    / \
   2   4
  /
 1

5.34.4 Constraints

  • The number of nodes in the tree is n
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

5.34.5 Solution - Reverse Inorder

5.34.5.1 Walkthrough

Use reverse inorder traversal (right → root → left) to visit nodes in descending order. Stop when we’ve visited k nodes.

Core Strategy:

In a BST, inorder traversal (left → root → right) visits nodes in ascending order. Reverse inorder (right → root → left) visits them in descending order. The k-th node visited is the k-th largest.

Example: Find 3rd largest in [5,3,6,2,4,null,null,1]:

Reverse inorder: 6 → 5 → 4 → 3 → 2 → 1
                 1st   2nd   3rd (return 4)

5.34.5.2 Analysis

  • Time Complexity: O(h + k) - Traverse to rightmost, then k steps back
  • Space Complexity: O(h) - Stack stores at most h nodes

5.34.5.3 Implementation Steps

  1. Use iterative traversal with a stack.
  2. Go right as far as possible (to largest element).
  3. Pop and decrement k; if k becomes 0, return current value.
  4. Then go left to continue in descending order.

5.34.5.4 Code - Java

public int kthLargest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.right;
        }
        current = stack.pop();
        if (--k == 0) {
            return current.val;
        }
        current = current.left;
    }
    return -1;
}