57.Kth Smallest Element in a BST
Problem
Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) among all node values in the tree.
Examples
Input: root = [3,1,4,null,2], k = 1
Output: 1Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: Sorted values are 1, 2, 3, 4, 5, 6; the 3rd is 3.Constraints
- The number of nodes in the tree is
n. 1 <= k <= n <= 10^40 <= Node.val <= 10^4
Follow-up: if the BST is modified often (inserts/deletes) and you need the k-th smallest frequently, store the size of each subtree in its node; then each query takes O(h).
💡 Key Insight
An in-order traversal of a BST visits values in ascending order. So the k-th node popped by in-order is the answer. With an explicit stack we can stop as soon as we have popped k nodes, doing only O(h + k) work instead of traversing the whole tree.
Brute Force (Collect and Sort)
TimeO(n log n)SpaceO(n)Intuition
Ignore the BST property: gather every value with any traversal, sort the list, and index position k - 1.
Algorithm
- Traverse the tree and append every value to
values. - Sort
values. - Return
values.get(k - 1).
Visualization
root = [5,3,6,2,4,null,null,1]
pre-order collect: [5, 3, 2, 1, 4, 6]
sorted: [1, 2, 3, 4, 5, 6]
k = 3 -> index 2 -> 3Code
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> values = new ArrayList<>();
collect(root, values);
Collections.sort(values);
return values.get(k - 1);
}
private void collect(TreeNode node, List<Integer> values) {
if (node == null) {
return;
}
values.add(node.val);
collect(node.left, values);
collect(node.right, values);
}
}Complexity
- Time: O(n log n) — dominated by sorting.
- Space: O(n) — the list of values.
Recursive In-Order with Counter
TimeO(h + k)SpaceO(h)Intuition
In-order traversal already produces sorted order, so no sort is needed. Count nodes as they are visited in-order; the node at which the counter reaches k holds the answer. Once found, the remaining calls return immediately.
Algorithm
- Keep fields
count = 0andanswer. inorder(node): ifnodeisnullor the answer is found, return.inorder(node.left).- Increment
count; ifcount == k, recordanswer = node.valand return. inorder(node.right).
- Return
answer.
Visualization
in-order visit order: 1, 2, 3, 4, 5, 6
count: 1 2 3 -> stop, answer 3Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int count = 0;
private int answer = -1;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return answer;
}
private void inorder(TreeNode node, int k) {
if (node == null || count >= k) {
return; // nothing left to do once the answer is found
}
inorder(node.left, k);
count++;
if (count == k) {
answer = node.val;
return;
}
inorder(node.right, k);
}
}Complexity
- Time: O(h + k) — we descend to the minimum and then visit
knodes (O(n) worst case). - Space: O(h) — recursion depth.
Iterative In-Order with StackOptimal
TimeO(h + k)SpaceO(h)Intuition
The same traversal, made explicit. Push the whole left spine (those are smaller values waiting to be visited), pop the smallest remaining node, then move to its right subtree and push that subtree's left spine. The k-th pop is the answer, and we return on the spot — no global state, no extra calls after the answer is found.
Algorithm
cur = root, empty stack.- Loop:
- While
cur != null: pushcur,cur = cur.left. cur = stack.pop(); decrementk; ifk == 0, returncur.val.cur = cur.right.
- While
Dry Run
flowchart TD
A["push 5, 3, 2, 1<br/>stack: 5 3 2 1"] --> B["pop 1 (k=3 -> 2)<br/>1.right = null"]
B --> C["pop 2 (k=2 -> 1)<br/>2.right = null"]
C --> D["pop 3 (k=1 -> 0)"]
D --> E["k == 0 -> return 3"]Code
import java.util.ArrayDeque;
import java.util.Deque;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (true) {
// push the left spine: smaller values come first
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop(); // next value in ascending order
if (--k == 0) {
return cur.val;
}
cur = cur.right;
}
}
}Complexity
- Time: O(h + k) — descend the left spine, then pop exactly
knodes. - Space: O(h) — the stack holds at most one root-to-leaf path.
Complexity Comparison
| Approach | Time | Space |
|---|---|---|
| Brute Force (Collect and Sort) | O(n log n) | O(n) |
| Recursive In-Order with Counter | O(h + k) | O(h) |
| Iterative In-Order with Stack | O(h + k) | O(h) |
Common Pitfalls
- Off-by-one:
kis 1-indexed, so the answer isvalues.get(k - 1)or the pop wherekreaches0. - Using pre-order or level order and expecting sorted output — only in-order is sorted for a BST.
- In the recursive version, not stopping after finding the answer — the traversal keeps running, and if
answeris overwritten later you get the wrong value. - Declaring
countasstatic— it carries over between LeetCode test cases.