Binary Search TreesProblem 12 of 22

Find Kth largest element in a BST

Brute Force
Time: O(n)
Space: O(n)
Optimal
Time: O(h + k)
Space: O(h)

Problem Statement

Given a BST and a positive integer k, find the kth largest element in the BST.

Example:

5 / \ 3 6 / \ 2 4 / 1 k = 2 Output: 5 (Elements in desc order: 6, 5, 4, 3, 2, 1) k = 4 Output: 3

Approach 1: Brute Force (Inorder + Find kth from End)

Intuition

Inorder traversal gives sorted order. The kth largest is the (n-k+1)th element or simply the kth element from the end.

Algorithm

  1. Perform inorder traversal to get sorted array
  2. Return array[n - k] (0-indexed) which is kth largest
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private void inorder(TreeNode root, List<Integer> nodes) {
        if (root == null) return;
        inorder(root.left, nodes);
        nodes.add(root.val);
        inorder(root.right, nodes);
    }
    
    public int kthLargestBruteForce(TreeNode root, int k) {
        List<Integer> nodes = new ArrayList<>();
        inorder(root, nodes);
        
        if (k > nodes.size() || k <= 0) {
            return -1;  // Invalid k
        }
        
        return nodes.get(nodes.size() - k);
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Complete traversal
  • Space Complexity: O(n) - Storing all nodes

Approach 2: Optimal (Reverse Inorder Traversal)

Intuition

Reverse inorder (right -> root -> left) visits nodes in descending order. Stop when we reach the kth node.

Algorithm

  1. Perform reverse inorder traversal
  2. Count nodes visited
  3. When count equals k, record the result
  4. Use early termination to avoid unnecessary traversal
java
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int count = 0;
    private int result = -1;
    
    private void reverseInorder(TreeNode root, int k) {
        if (root == null || count >= k) return;
        
        // Traverse right subtree first (larger values)
        reverseInorder(root.right, k);
        
        // Process current node
        count++;
        if (count == k) {
            result = root.val;
            return;
        }
        
        // Traverse left subtree
        reverseInorder(root.left, k);
    }
    
    public int kthLargest(TreeNode root, int k) {
        count = 0;
        result = -1;
        reverseInorder(root, k);
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(h + k) - Traverse to rightmost then k nodes
  • Space Complexity: O(h) - Recursion stack

Approach 3: Iterative (Morris-like with Stack)

Intuition

Use iterative reverse inorder with explicit stack for O(h) space.

Algorithm

  1. Use stack to simulate reverse inorder
  2. Push right nodes first, then process, then go left
  3. Stop at kth node
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int kthLargestIterative(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        int count = 0;
        
        while (curr != null || !stack.isEmpty()) {
            // Go to rightmost
            while (curr != null) {
                stack.push(curr);
                curr = curr.right;
            }
            
            curr = stack.pop();
            
            count++;
            if (count == k) {
                return curr.val;
            }
            
            curr = curr.left;
        }
        
        return -1;  // k is larger than tree size
    }
}

Complexity Analysis

  • Time Complexity: O(h + k)
  • Space Complexity: O(h) - Stack space

Approach 4: Using Augmented BST (For Multiple Queries)

Intuition

If we need to answer multiple kth largest/smallest queries, augment each node with the count of nodes in its subtree.

Algorithm

  1. Augment each node with size of its subtree
  2. For kth largest: k nodes from the right
  3. Use subtree sizes to navigate efficiently
java
class AugmentedNode {
    int val;
    int leftCount;  // Number of nodes in left subtree
    AugmentedNode left, right;
    AugmentedNode(int x) { val = x; leftCount = 0; }
}

public class Solution {
    private int countNodes(AugmentedNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    private void augmentTree(AugmentedNode root) {
        if (root == null) return;
        root.leftCount = countNodes(root.left);
        augmentTree(root.left);
        augmentTree(root.right);
    }
    
    private AugmentedNode kthSmallestAugmented(AugmentedNode root, int k) {
        if (root == null) return null;
        
        int leftCount = root.leftCount;
        
        if (k == leftCount + 1) {
            return root;
        } else if (k <= leftCount) {
            return kthSmallestAugmented(root.left, k);
        } else {
            return kthSmallestAugmented(root.right, k - leftCount - 1);
        }
    }
    
    public int kthLargestAugmented(AugmentedNode root, int k, int n) {
        AugmentedNode node = kthSmallestAugmented(root, n - k + 1);
        return node != null ? node.val : -1;
    }
}

Complexity Analysis

  • Time Complexity: O(h) per query after O(n) preprocessing
  • Space Complexity: O(n) for augmented data

Key Takeaways

  1. Reverse inorder: Right-Root-Left gives descending order
  2. Early termination: Stop once kth element is found
  3. Relation to kth smallest: kth largest = (n-k+1)th smallest
  4. Augmented BST: O(h) queries for multiple kth element queries
  5. This is similar to LeetCode #230 (kth smallest) with reverse traversal
  6. Iterative version avoids recursion stack overflow for large trees
  7. For single query, O(h+k) is optimal; for multiple queries, augment the tree
Previous
Merge two BST [V.V.V.IMP]
Next
Find Kth smallest element in a BST