Kth Smallest Element in a BST
Given the root of a BST and an integer k, return the k-th smallest value (1-indexed) among all node values.
Constraints:
- The number of nodes is
n, with1 <= k <= n <= 10^4. 0 <= Node.val <= 10^4
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14The inorder traversal (Left, Root, Right) of a BST visits values in sorted order: 2, 4, 6, 8, 10, 12, 14. So the k-th smallest is simply the k-th node visited in inorder. For k = 3 the answer is 6.
There is no need to collect everything into a list. We can stop the moment we reach the k-th node.
Approach: Iterative Inorder, Stop at k
Use the iterative inorder from the traversals module:
- Keep a stack and a pointer
nodestarting at the root. - While
nodeexists or the stack is not empty:- Push
nodeand go left untilnull. - Pop a node. This is the next value in sorted order. Decrement
k. Ifkreaches 0, return this node's value. - Move to the popped node's right child.
- Push
This finishes after about h + k steps instead of walking the whole tree.
Code
class Solution {public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> st;TreeNode* node = root;while (node != nullptr || !st.empty()) {while (node != nullptr) {st.push(node);node = node->left;}node = st.top();st.pop();if (--k == 0) return node->val;node = node->right;}return -1;}};
Complexity
Time: O(h + k)
We go down to the leftmost node (h steps) and then pop k nodes in sorted order. Worst case it is O(n).
Space: O(h)
The stack holds the current left 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 traversal of a BST gives the values in sorted order, so the k-th smallest is the k-th node visited in inorder. I do an iterative inorder with a stack: push the left spine, pop a node, decrement k, and return as soon as k hits zero, otherwise move to the right child. I do not need to collect the whole traversal, so I stop early. Time is O of h plus k and space is O of h for the stack. A Morris inorder would bring the space down to O of one."
Next TopicKth Largest Element in a BST