Difficulty: Medium Pattern: Trees LeetCode: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
Given the root of a binary search tree and an integer k, return the k-th smallest value among
all node values (1-indexed).
Signature:
int kthSmallest(TreeNode root, int k)
Examples:
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
A binary search tree (BST) is like a sorted filing cabinet arranged as a tree: everything in a node’s left subtree is smaller, everything in its right subtree is larger. If you visit the files in a special order – left subtree first, then the node itself, then the right subtree – you read them out in ascending order. That order is called an inorder traversal (one of the three depth-first orderings on a tree; see Preorder / Inorder / Postorder). So “the kth smallest value” is simply “the kth node an inorder walk visits.”
Trace root = [5,3,6,2,4,null,null,1], k = 3:
5
/ \
3 6
/ \
2 4
/
1
Inorder always goes leftmost first. From 5, go left to 3, left to 2, left to 1 – no
left child, so visit 1. Back up to 2 (visit), back to 3 (visit), then right to 4
(visit). Back up to 5 (visit), then right to 6 (visit). The visit order is
1, 2, 3, 4, 5, 6. The 3rd node visited is 3 – the answer.
We could collect the whole visit sequence into a list and read index k-1, but that does more
work than needed. Instead we run the inorder walk iteratively with an explicit
stack (last-in-first-out), so we can stop the instant
we have visited k nodes. Here is the mechanic, which simulates exactly what the recursive
version would do:
k); if k hits 0, return its value immediately.The reason this yields sorted order: the leftmost unvisited node is always the smallest one
remaining, and popping it before any of its ancestors (which hold larger values) keeps the
visit sequence ascending. The early return at k == 0 means that on average we touch far
fewer than n nodes.
Pause and answer before expanding. Wrong guesses teach more than fast right ones.
Q1 (recall). Which traversal visits a BST’s values in ascending sorted order?
Q2 (comprehend). Why does the iterative version stop the moment k hits 0, instead of collecting the whole inorder sequence?
function kthSmallest(root, k):
stack = empty stack
node = root
while stack is not empty or node is not null:
while node is not null: # walk all the way left, pushing each
push node onto stack
node = node.left
node = stack.pop() # next node in sorted order
decrement k
if k == 0:
return node.value # early exit
node = node.right # then go right, and resume the left-walk
# k was larger than the node count
The inner while dives left as far as possible; each pop yields the next value in sorted order;
moving to the right child after a pop is what makes the traversal resume correctly.
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
k--;
if (k == 0) {
return node.val;
}
node = node.right;
}
throw new IllegalArgumentException("k is larger than the number of nodes");
}
}
ArrayDeque serves as the stack (the book’s preferred LIFO, 03-java-crash-course.md section 4).
The outer loop condition !stack.isEmpty() || node != null is the standard iterative-inorder
guard: we keep going while there is either a suspended ancestor on the stack or a node to descend
into. Decrementing k on each pop and returning immediately at 0 is the early-exit – on
average we touch far fewer than n nodes. The trailing throw is unreachable on valid input but
satisfies the compiler and documents the precondition.
Time: O(h + k) -- O(h) to reach the first (leftmost) node, then k pops to find the answer;
O(n) worst case when k is the largest element
Space: O(h) -- stack holds at most one root-to-leaf path (log n balanced, n skewed)
Tree [5,3,6,2,4,null,null,1], k = 3:
5
/ \
3 6
/ \
2 4
/
1
Inorder order: 1, 2, 3, 4, 5, 6.
| Step | action | stack (top right) | node | k after |
|---|---|---|---|---|
| 1 | dive left from 5 | [5, 3, 2, 1] | null | 3 |
| 2 | pop 1 | [5, 3, 2] | 1 | 2 |
| 3 | 1.right is null; pop 2 | [5, 3] | 2 | 1 |
| 4 | 2.right is null; pop 3 | [5] | 3 | 0 |
k == 0 after popping node 3 -> return 3.
Q1 (apply). Trace this BST with k = 4:
4
/ \
2 5
/ \
1 3
Inorder visits 1, 2, 3, 4, 5. What is returned?
345Q2 (analyze). What happens if you forget the node = node.right step after a pop?
Q3 (transfer). How would you find the KTH LARGEST element instead of the kth smallest, reusing the same idea? Outline it in words.
[k-1]. Correct but O(n) time and
O(n) space always; the iterative early-exit is faster on average and uses only O(h) space.node = node.right step after a pop. Without it the traversal collapses to a
left-spine walk and misses every right subtree.