Trees · LC #230
Kth Smallest Element in BST
Return the kth smallest value in a BST by leveraging BST inorder traversal which yields values in sorted ascending order. Stop at the kth visited node.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Sample I/O
Input: root=[3,1,4,null,2], k=1 Output: 1 Input: root=[5,3,6,2,4,null,null,1], k=3 Output: 3
Time: O(h+k) · Space: O(h)
Intuition
How to Think About It
Intuition
BST inorder traversal (left → root → right) visits nodes in ascending sorted order. The kth node visited is the kth smallest - no sorting needed, just count visits during traversal.
Core Concept
Iterative inorder using explicit stack: push left spine onto stack, pop node, increment counter, return if counter == k, then move to right child. Recursive variant uses class-level counter but iterative is preferred for early exit efficiency.
When to use
BST order-statistic queries (kth smallest/largest), rank queries, BST-to-sorted-array conversion.
When NOT to use
Non-BST trees (inorder is not sorted). For frequent kth queries with updates, augment BST with subtree-size counts for O(h) queries.
Key Insights
What to Know Cold
- BST inorder = sorted ascending - this is the fundamental BST property being exploited.
- Early exit at count == k avoids traversing the entire tree.
- Iterative stack approach is better than recursive for early exit (no need to unwind call stack).
- O(h + k) time: O(h) to reach leftmost, then O(k) steps.
- For kth largest: reverse inorder (right → root → left) or use k = n - k + 1.
1 example
Worked Examples
Find 1st smallest
BST [3,1,4,null,2], k=1 - leftmost node is the minimum.
Iterative inorder: push 3,1. Pop 1 → count=1 == k=1 → return 1.
function kthSmallest(root: TreeNode | null, k: number): number {
const stack: TreeNode[] = [];
let curr = root, count = 0;
while (curr || stack.length) {
while (curr) { stack.push(curr); curr = curr.left; }
curr = stack.pop()!;
if (++count === k) return curr.val;
curr = curr.right;
}
return -1;
}Output: 1
Iterative early-exit pattern is more efficient than recursive for large trees.