On this page

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, with 1 <= k <= n <= 10^4.
  • 0 <= Node.val <= 10^4

Intuition

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

The 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:

  1. Keep a stack and a pointer node starting at the root.
  2. While node exists or the stack is not empty:
    • Push node and go left until null.
    • Pop a node. This is the next value in sorted order. Decrement k. If k reaches 0, return this node's value.
    • Move to the popped node's right child.

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