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 82 / \3 4 124 / \ / \5 2 6 10 14The 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
- Keep a stack and a pointer
nodeat the root. - While
nodeexists or the stack is not empty:- Push
nodeand go right untilnull. - Pop a node. This is the next largest value. Decrement
k. Ifkis 0, return its value. - Move to the popped node's left child.
- Push
- 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
We descend the right spine (h steps) and then pop k nodes in descending order. Worst case it is O(n).
The stack holds the current right spine, at most the tree height.