On this page

Kth Largest Element in a BST

Given the root of a BST and an integer k, return the k-th largest value among all node values. Assume 1 <= k <= n, where n is the number of nodes (return -1 if k is out of range).

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

The k-th largest is the k-th smallest counted from the other end. For k = 2 the answer in the tree above is 12 (sorted: 2, 4, 6, 8, 10, 12, 14).

Inorder (Left, Root, Right) gives ascending order. If we reverse it to Right, Root, Left, we get descending order, so the k-th node visited in a reverse inorder is the k-th largest.

A tempting shortcut is "it is the (n - k + 1)-th smallest", but that needs the node count first, which costs an extra pass. Reverse inorder avoids it.

Approach: Reverse Iterative Inorder, Stop at k

  1. Keep a stack and a pointer node at the root.
  2. While node exists or the stack is not empty:
    • Push node and go right until null.
    • Pop a node. This is the next largest value. Decrement k. If k is 0, return its value.
    • Move to the popped node's left child.
  3. If the loop ends, return -1.

It is the kth-smallest solution with left and right swapped.

Code

class Solution {
public:
int kthLargest(Node* root, int k) {
stack<Node*> st;
Node* node = root;
while (node != nullptr || !st.empty()) {
while (node != nullptr) {
st.push(node);
node = node->right;
}
node = st.top();
st.pop();
if (--k == 0) return node->data;
node = node->left;
}
return -1;
}
};

Complexity

Time: O(h + k)

We descend the right spine (h steps) and then pop k nodes in descending order. Worst case it is O(n).

Space: O(h)

The stack holds the current right spine, at most the tree height.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Inorder on a BST is ascending, so a reverse inorder, right then node then left, is descending. The k-th node visited in a reverse inorder is therefore the k-th largest. I do it iteratively with a stack: push the right spine, pop a node, decrement k, and return when it reaches zero, otherwise go to the left child. This avoids computing n minus k plus one, which would need an extra pass to count the nodes. Time is O of h plus k and space is O of h."
Next TopicValidate Binary Search Tree