Log inSign up
mediumGeeksforGeeksNot Started

Kth Largest Element in a BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a Binary Search Tree (BST) and an integer k, find the `k`-th largest element in the BST.

For example, if the BST contains the values [4, 8, 10, 12, 14, 20, 22] and k = 2, the 2nd largest element is 20.

Constraints:

  • 1 <= k <= Number of nodes in BST
  • 1 <= Number of nodes <= 105
  • 1 <= Node.data <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize symmetry between inorder (ascending) and reverse inorder (descending).
  • Implement early-exit reverse DFS with global/counter references.
  • Eliminate recursion stack frames using Reverse Morris Traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find k-th largest in Binary Search Tree.
  • Order statistic query on BST.
  • Avoid full tree traversal.

Algorithmic Decision Tree:

  • Reverse inorder: Explore right first, process root, then explore left.
  • Decrement k; when k == 0, capture ans = curr.data and terminate.

Connected Patterns:

Kth Smallest Element in a BSTConvert BST to Greater TreeBinary Search Tree Iterator

1. Standard Inorder Array Collection

Intuition

Perform a full inorder traversal of the BST, appending each visited node's data to an array. Since inorder traversal produces a sorted list of length N, the k-th largest element is located at index N - k. Return arr[N - k].

When to apply: Baseline comparison when tree size is small and code simplicity is preferred.

Algorithm

  1. Collect all elements in ascending order via inorder traversal into an array, then return the (N - k)-th element.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct Node {
5 int data;
6 Node* left;
7 Node* right;
8 Node(int val) : data(val), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(Node* root, std::vector<int>& vals) {
13 if (!root) return;
14 inorder(root->left, vals);
15 vals.push_back(root->data);
16 inorder(root->right, vals);
17 }
18public:
19 int kthLargest(Node* root, int k) {
20 std::vector<int> vals;
21 inorder(root, vals);
22 int n = vals.size();
23 return vals[n - k];
24 }
25};
26
27int main() {
28 Node* root = new Node(20);
29 root->left = new Node(8);
30 root->right = new Node(22);
31 root->left->left = new Node(4);
32 root->left->right = new Node(12);
33 root->left->right->left = new Node(10);
34 root->left->right->right = new Node(14);
35
36 Solution sol;
37 std::cout << "3rd largest: " << sol.kthLargest(root, 3) << std::endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N) auxiliary space

2. Reverse Inorder Recursive DFS with Early Exit

Intuition

Traverse the tree using reverse inorder: 1. Recurse right subtree first: reverseInorder(root.right). 2. Process current node: decrement k. If k == 0, save ans = root.data and return. 3. Recurse left subtree: reverseInorder(root.left). Stop recursion as soon as ans is found.

When to apply: The standard interview approach when recursion stack memory is permitted.

Algorithm

  1. Traverse Right -> Root -> Left recursively. Decrement k and return immediately once k reaches 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11 int count = 0;
12 int result = -1;
13
14 void reverseInorder(Node* root, int k) {
15 if (!root || count >= k) return;
16
17 reverseInorder(root->right, k);
18
19 count++;
20 if (count == k) {
21 result = root->data;
22 return;
23 }
24
25 reverseInorder(root->left, k);
26 }
27public:
28 int kthLargest(Node* root, int k) {
29 count = 0;
30 result = -1;
31 reverseInorder(root, k);
32 return result;
33 }
34};
35
36int main() {
37 Node* root = new Node(20);
38 root->left = new Node(8);
39 root->right = new Node(22);
40 root->left->left = new Node(4);
41 root->left->right = new Node(12);
42 root->left->right->left = new Node(10);
43 root->left->right->right = new Node(14);
44
45 Solution sol;
46 std::cout << "3rd largest: " << sol.kthLargest(root, 3) << std::endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(H + k) where H is tree height
  • Space complexity: O(H) recursion stack space

3. Reverse Morris Traversal (O(1) Auxiliary Space)

Intuition

Mirror Morris Inorder Traversal to visit nodes in descending order: 1. If curr.right == null, decrement k; if k == 0 save result, then move curr = curr.left. 2. If curr.right != null, find inorder successor in reverse traversal (leftmost node in curr.right). If succ.left == null, make thread succ.left = curr; curr = curr.right. If succ.left == curr, restore thread succ.left = null, decrement k, and move curr = curr.left. Clean up all threads before exiting.

When to apply: When strictly O(1) auxiliary space is mandated.

Algorithm

  1. Traverse Right -> Root -> Left using threaded binary tree pointers without recursion stack or heap allocation.

Reverse Inorder Search Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
count = 1
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
Recurse right to Node(22). 22 is leaf. Visit 22.
Decision / next transition
1
Why this step matters

count = 1. k = 3.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int kthLargest(Node* root, int k) {
13 Node* curr = root;
14 int count = 0;
15 int result = -1;
16
17 while (curr) {
18 if (!curr->right) {
19 count++;
20 if (count == k) result = curr->data;
21 curr = curr->left;
22 } else {
23 Node* succ = curr->right;
24 while (succ->left && succ->left != curr) {
25 succ = succ->left;
26 }
27
28 if (!succ->left) {
29 succ->left = curr; // make thread
30 curr = curr->right;
31 } else {
32 succ->left = nullptr; // break thread
33 count++;
34 if (count == k) result = curr->data;
35 curr = curr->left;
36 }
37 }
38 }
39 return result;
40 }
41};
42
43int main() {
44 Node* root = new Node(20);
45 root->left = new Node(8);
46 root->right = new Node(22);
47 root->left->left = new Node(4);
48 root->left->right = new Node(12);
49 root->left->right->left = new Node(10);
50 root->left->right->right = new Node(14);
51
52 Solution sol;
53 std::cout << "3rd largest: " << sol.kthLargest(root, 3) << std::endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Standard Inorder Array CollectionO(N)O(N) auxiliary spaceCollect all elements in ascending order via inorder traversal into an array, then return the (N - k)-th element.O(N)
2.Reverse Inorder Recursive DFS with Early ExitO(H + k) where H is tree heightO(H) recursion stack spaceTraverse Right -> Root -> Left recursively. Decrement k and return immediately once k reaches 0.O(H + k) where H is tree height
3.Reverse Morris Traversal (O(1) Auxiliary Space)OptimalO(N)O(1) auxiliary spaceTraverse Right -> Root -> Left using threaded binary tree pointers without recursion stack or heap allocation.O(N)

Common Pitfalls & Crucial Edge Cases

Forgetting to reset static/instance variables

If count is a class variable, reusing it across multiple test cases produces wrong results.

Traversing left child first

Computes k-th smallest instead of k-th largest.

Index error in array approach

Using arr[k] or arr[k - 1] instead of arr[N - k].

Crucial Edge Cases to Validate:

  • k = 1 — Returns the maximum element (rightmost node).
  • k = N — Returns the minimum element (leftmost node).
  • Single node tree (N = 1, k = 1) — Returns the root node value.
  • Skewed BST — Traversal works correctly without skipping any nodes.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the duality: Standard Inorder is ascending, Reverse Inorder (Right -> Node -> Left) is descending.
  2. State how early-exit reduces time from O(N) to O(H + k).
  3. Offer the Reverse Morris Traversal as an O(1) space extension.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is Reverse Inorder Traversal (Right -> Root -> Left) preferred over Standard Inorder for finding the k-th largest element?

2.If k = 1, what node in the BST is the 1st largest?

3.What is the worst-case space complexity of recursive Reverse Inorder on a left-skewed BST?

Back to DSA Sheet