#230
Kth Smallest Element in a BST
Medium Inorder with a counter
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the k-th smallest value (1-indexed) in a BST.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the k-th smallest value.
Why this works: inorder visits values in increasing order; stop at the k-th visit.
Example: 3 (1 (-, 2), 4), k = 1
inorder: 1 → first → answer 1✦Hints open one at a time
Inorder traversal visits values in increasing order.
Stop as soon as you've visited k nodes.
↗Approach
Iterative inorder with a stack; decrement k on each visit and return when it reaches 0.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
while (true) {
while (cur != null) {
st.push(cur);
cur = cur.left;
}
cur = st.pop();
if (--k == 0) return cur.val; // k-th visit in sorted order
cur = cur.right;
}
}
}!Common mistake
Collecting all values into a list first — O(n) even when k is small.
Complexity
- Time: O(h + k).
- Space: O(h).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon