Kth Smallest Element in BST
Mahabharata — The kth Rank — Finding the kth Weakest Warrior in the Sorted Formation
Inorder में BST — क्रमबद्ध। k वां तत्व — गिनते जाओ, मिलने पर रुको॥
*Inorder of BST — sorted. The kth element — count as you go, stop when found.*
The Story
Find the kth smallest element in a BST.
For BST `[3,1,4,null,2]`, k=1: answer=1 (smallest). For BST `[5,3,6,2,4,null,null,1]`, k=3: answer=3.
**Inorder traversal counts to k:** BST inorder gives elements in sorted order. The kth element in inorder is the kth smallest.
**Iterative inorder with early stop:** ```java public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> st = new ArrayDeque<>(); int count = 0; while (root != null || !st.isEmpty()) { while (root != null) { st.push(root); root = root.left; } // Go deep left root = st.pop(); if (++count == k) return root.val; // kth visit! root = root.right; } return -1; // Not found } ```
**Recursive with counter:** ```java int count = 0, result = 0; void inorder(TreeNode root, int k) { if (root == null) return; inorder(root.left, k); if (++count == k) { result = root.val; return; } inorder(root.right, k); } ```
Trace BST `[3,1,4,null,2]`, k=1: - Push 3, push 1, left of 1 is null. Pop 1, count=1==k=1 → return 1 ✓
O(h+k): we go down h levels to reach the leftmost (smallest), then count k nodes up.
The Full Inorder Collection
Collect all values via inorder into a list, return list[k-1]. O(n) time and space.
public int kthSmallestBrute(TreeNode root, int k) {
List<Integer> list = new ArrayList<>();
inorder(root, list);
return list.get(k - 1);
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) return;
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}The Inorder-Count-to-k Wisdom
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> st = new ArrayDeque<>();
int count = 0;
while (root != null || !st.isEmpty()) {
while (root != null) { st.push(root); root = root.left; }
root = st.pop();
if (++count == k) return root.val;
root = root.right;
}
return -1;
}Step-by-Step Walkthrough
BST=[1,null,2], k=2: push 1, left=null. pop 1, count=1≠2. right=2. push 2, left=null. pop 2, count=2==2 → return 2 ✅
Deep Insight
**O(h+k) vs O(n):** The iterative approach stops as soon as we've counted k nodes. We push h nodes going to the leftmost, then pop k nodes counting up. Total: O(h+k). For a balanced BST: O(log n + k). The brute force collects all n nodes: O(n).
**Augmented BST for O(log n):** Store `leftSize` (size of left subtree) at each node. Then: - If k == leftSize+1: root is kth - If k <= leftSize: recurse left with same k - If k > leftSize+1: recurse right with k-(leftSize+1) This enables O(log n) per query but requires augmenting the BST.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Full inorder collection |
| Optimal | O(h + k) | O(h) | Early stop iterative; O(log n + k) for balanced BST |
Pattern Recognition
✅ Kth smallest in BST = inorder + count to k ✅ Early stop: return when count==k ✅ Iterative for O(h) space ✅ Augmented BST for O(log n) if needed **LeetCode Trigger Phrases:** → "kth smallest element in BST" → BST inorder with early termination → Rank in BST
Bhagavad Gita 7.3
मनुष्याणां सहस्रेषु कश्चिद्यतति सिद्धये। यततामपि सिद्धानां कश्चिन्मां वेत्ति तत्त्वतः॥
Among thousands of men, perhaps one strives for perfection; among those who strive and succeed, perhaps one knows Me in truth.
Connection: Finding the kth smallest in a BST is about counting — stopping at exactly the right rank. Like the Gita's observation that only a rare few among thousands achieve true knowledge, the kth smallest element occupies a specific rank among all elements. The inorder traversal counts each element in ascending order, stopping at precisely the kth — the one whose rank we seek, neither above nor below.