Kth Smallest Element in a BST (LeetCode 230)
You get the root of a binary search tree and a whole number k. Imagine writing every value in the tree in a row, smallest first, and numbering the positions from 1: return the value that lands in position k.
In a binary search tree, the values in a node's left subtree are smaller than the node's value, and the values in its right subtree are larger.
Follow-up: if nodes are inserted and deleted often and this question is asked again and again, how would you make each answer faster?
Worked Examples
root = [3,1,4,null,2], k = 111, 2, 3, 4. Position 1 holds 1, a leaf on the left, even though 3 sits at the top of the tree.root = [5,3,6,2,4,null,null,1], k = 331, 2, 3, 4, 5, 6, so position 3 holds 3.⚖️Formal Constraints & Bounds
The number of nodes in the tree is
n.1 <= k <= n <= 1040 <= Node.val <= 104
Core Insight
Rank in a BST is position in sorted order, and the inorder walk produces sorted order one value per visit, so the k-th visit is the answer and the walk can stop there.
Real-World Scenario & Production Applications
Rank queries on ordered data are everywhere: the 10th cheapest listing, the median of a set of latency samples, the k-th oldest open ticket. When the data already sits in a search tree it is sorted in place, so walking it in order and stopping at the k-th item beats copying everything out and sorting it again.
Step-by-Step Execution Trace Table
Example 2, root = [5,3,6,2,4,null,null,1], k = 3:
| Step | What runs | stack (bottom to top) | node | k | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [5, 3, 2, 1] | None | 3 | Four nodes pushed, none counted: pushing is not visiting |
| 2 | node = stack.pop(), k -= 1 | [5, 3, 2] | 1 | 2 | 1st visit: 1 is the smallest value |
| 3 | node = node.right is None; pop, k -= 1 | [5, 3] | 2 | 1 | 2nd visit |
| 4 | node = node.right is None; pop, k -= 1 | [5] | 3 | 0 | 3rd visit: k == 0, return 3 |
Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.
root = [3,1,4,null,2], k = 11Example 2, root = [5,3,6,2,4,null,null,1], k = 3:
| Step | What runs | stack (bottom to top) | node | k | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [5, 3, 2, 1] | None | 3 | Four nodes pushed, none counted: pushing is not visiting |
| 2 | node = stack.pop(), k -= 1 | [5, 3, 2] | 1 | 2 | 1st visit: 1 is the smallest value |
| 3 | node = node.right is None; pop, k -= 1 | [5, 3] | 2 | 1 | 2nd visit |
| 4 | node = node.right is None; pop, k -= 1 | [5] | 3 | 0 | 3rd visit: k == 0, return 3 |
Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.
| 1 | Rank in a BST is position in sorted order, and an inorder walk (left subtree, node, right subtree) visits the values in sorted order: the answer is the `k`-th visit. |
| 2 | When `stack.pop()` returns `node`, every smaller value has already been visited, so do `k -= 1` there and `return node.val` when `k == 0`. |
| 3 | Start with `stack = []` and `node = root`, and loop `while node or stack`: an inner `while node` pushes and moves to `node.left`, then pop, count, and move to `node.right`. |
| 4 | The trap: count on the pop, never on the push. Nodes are pushed from the root down, so counting pushes on `[3,1,4,null,2]` returns 3 for `k = 1`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The k-th smallest value sounds like a job for sorting: copy every value out, sort, and index. A BST makes that unnecessary, because it is already sorted, just not in a line. Every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger, so the order left subtree, node, right subtree (an inorder walk) visits the values from smallest to largest. BST Inorder reads the tree as that sorted list, one value per visit, and stops as soon as it has what it needs.
📚 The Analogy: A Library Shelved by Call Number
A library keeps its books in call-number order along branching aisles: every aisle to your left holds smaller numbers, every aisle to your right larger ones. To find the 10th book in call-number order, you don't pull every book off the shelves and sort them. You walk to the far left end, then walk the aisles in order, counting books as you pass them, and stop at the 10th. On the way in you note each turn you skipped (the stack), so you can come back to it.
🔑 Why It Works
The inner loop dives left, pushing every node it passes, so the node that stack.pop() returns has no smaller value left unvisited: its left subtree is done, and so is every ancestor it sits to the right of. Each pop is therefore the next value in sorted order, and k -= 1 on the pop counts ranks exactly. Counting on the push instead would count nodes from the root down, which is not sorted order.
Counting
k -= 1when a node is pushedLooping
while stackinstead ofwhile node or stackPushing
node.rightstraight ontostackWalking every node when the nearest values are already found
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Binary search tree" plus "the k-th smallest value": rank means position in sorted order, and in a BST the inorder walk (left subtree, node, right subtree) already produces sorted order. When a BST question is about ranks, neighbouring values or the values nearest a target, that is the signal for BST Inorder.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision is made at each pop: k -= 1, and if k == 0, node.val is the answer; otherwise node = node.right and the walk goes on. k always counts the visits still needed.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: count on the pop (
k -= 1afterstack.pop()), not on the push.kis 1-indexed: runk -= 1before thek == 0test. Testing first returns the (k + 1)-th smallest value.Return inside the loop at
k == 0. Finishing the walk and remembering the k-th value is still correct, but it visits all n nodes instead of stopping after k.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use BST Inorder. In a binary search tree, visiting the left subtree, then the node, then the right subtree hands out the values in sorted order, so the k-th smallest is simply the k-th visit. I walk iteratively with a stack: going left, I push every node I pass, so when I pop a node, everything smaller than it has already been visited. On each pop I decrement k, and when k reaches zero I return that node's value; otherwise I continue from its right child. The trap is where I count: nodes are pushed from the root down, so counting pushes would return a value near the root instead of the k-th smallest. Counting pops keeps the count equal to the rank. I stop after k visits, so the time is O(H plus k), where H is the height of the tree, and the stack uses O(H) space.
Complexity & Mathematical Proof
O(H + k)
Look at the code: before the first visit, the inner while node: loop pushes the left edge of the tree, at most H nodes. After that, each pass of the outer loop visits one node with stack.pop() and k -= 1, and every node pushed along the way is either visited later or still on stack when the function returns. The walk returns at the k-th visit, so it makes at most k pops and at most H + k pushes, each O(1). Total: O(H + k).
O(H) stack
Every node on stack is an ancestor of node whose left subtree is still being walked, so stack holds at most one root-to-leaf path: O(H) nodes. The answer is one integer.
Derivation Progression
at most H pushes
Before the first visit, while node: pushes the left edge of the tree, one node per level.
k pops
Each pass of while node or stack: pops one node and runs k -= 1; the function returns at the k-th pop.
at most H + k pushes in total
Every pushed node is either popped (at most k of them) or still on stack at the return (at most H).
O(H + k)
Each push and pop is O(1).
Variable Definitions
Number of nodes in the tree
Height of the tree: about log n when balanced, up to n on a chain
The rank asked for, 1 <= k <= n
Memory Architecture & Bounds
O(1): iterative, no recursion
O(H): stack holds one root-to-leaf path at most
O(1): one integer
Boundary Best / Worst Cases
: k = 1, one dive down the left edge and a single visit
on a balanced tree
: k = n, or a chain of height
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "binary search tree", "the k-th smallest value". A rank question on a BST: BST Inorder, read as a stream that stops after k visits.
nodes, . Copying every value into a list and sorting costs time and memory; the iterative walk stops after k visits, so it costs time and only the stack, where is the tree height ( when balanced, up to on a chain).
A chain of nodes is levels deep: a recursive walk can overflow a small call stack, and the explicit stack avoids that. LeetCode's follow-up (many queries while nodes are inserted and deleted) calls for storing each node's subtree size, so one query walks a single root-to-leaf path in .
Kth Smallest Element in a BST (LeetCode 230)
You get the root of a binary search tree and a whole number k. Imagine writing every value in the tree in a row, smallest first, and numbering the positions from 1: return the value that lands in position k.
In a binary search tree, the values in a node's left subtree are smaller than the node's value, and the values in its right subtree are larger.
Follow-up: if nodes are inserted and deleted often and this question is asked again and again, how would you make each answer faster?
Worked Examples
root = [3,1,4,null,2], k = 111, 2, 3, 4. Position 1 holds 1, a leaf on the left, even though 3 sits at the top of the tree.root = [5,3,6,2,4,null,null,1], k = 331, 2, 3, 4, 5, 6, so position 3 holds 3.⚖️Formal Constraints & Bounds
The number of nodes in the tree is
n.1 <= k <= n <= 1040 <= Node.val <= 104
Core Insight
Rank in a BST is position in sorted order, and the inorder walk produces sorted order one value per visit, so the k-th visit is the answer and the walk can stop there.
Real-World Scenario & Production Applications
Rank queries on ordered data are everywhere: the 10th cheapest listing, the median of a set of latency samples, the k-th oldest open ticket. When the data already sits in a search tree it is sorted in place, so walking it in order and stopping at the k-th item beats copying everything out and sorting it again.
Step-by-Step Execution Trace Table
Example 2, root = [5,3,6,2,4,null,null,1], k = 3:
| Step | What runs | stack (bottom to top) | node | k | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [5, 3, 2, 1] | None | 3 | Four nodes pushed, none counted: pushing is not visiting |
| 2 | node = stack.pop(), k -= 1 | [5, 3, 2] | 1 | 2 | 1st visit: 1 is the smallest value |
| 3 | node = node.right is None; pop, k -= 1 | [5, 3] | 2 | 1 | 2nd visit |
| 4 | node = node.right is None; pop, k -= 1 | [5] | 3 | 0 | 3rd visit: k == 0, return 3 |
Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.
root = [3,1,4,null,2], k = 11Example 2, root = [5,3,6,2,4,null,null,1], k = 3:
| Step | What runs | stack (bottom to top) | node | k | What it means |
|---|---|---|---|---|---|
| 1 | Dive: stack.append(node), node = node.left | [5, 3, 2, 1] | None | 3 | Four nodes pushed, none counted: pushing is not visiting |
| 2 | node = stack.pop(), k -= 1 | [5, 3, 2] | 1 | 2 | 1st visit: 1 is the smallest value |
| 3 | node = node.right is None; pop, k -= 1 | [5, 3] | 2 | 1 | 2nd visit |
| 4 | node = node.right is None; pop, k -= 1 | [5] | 3 | 0 | 3rd visit: k == 0, return 3 |
Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.
| 1 | Rank in a BST is position in sorted order, and an inorder walk (left subtree, node, right subtree) visits the values in sorted order: the answer is the `k`-th visit. |
| 2 | When `stack.pop()` returns `node`, every smaller value has already been visited, so do `k -= 1` there and `return node.val` when `k == 0`. |
| 3 | Start with `stack = []` and `node = root`, and loop `while node or stack`: an inner `while node` pushes and moves to `node.left`, then pop, count, and move to `node.right`. |
| 4 | The trap: count on the pop, never on the push. Nodes are pushed from the root down, so counting pushes on `[3,1,4,null,2]` returns 3 for `k = 1`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The k-th smallest value sounds like a job for sorting: copy every value out, sort, and index. A BST makes that unnecessary, because it is already sorted, just not in a line. Every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger, so the order left subtree, node, right subtree (an inorder walk) visits the values from smallest to largest. BST Inorder reads the tree as that sorted list, one value per visit, and stops as soon as it has what it needs.
📚 The Analogy: A Library Shelved by Call Number
A library keeps its books in call-number order along branching aisles: every aisle to your left holds smaller numbers, every aisle to your right larger ones. To find the 10th book in call-number order, you don't pull every book off the shelves and sort them. You walk to the far left end, then walk the aisles in order, counting books as you pass them, and stop at the 10th. On the way in you note each turn you skipped (the stack), so you can come back to it.
🔑 Why It Works
The inner loop dives left, pushing every node it passes, so the node that stack.pop() returns has no smaller value left unvisited: its left subtree is done, and so is every ancestor it sits to the right of. Each pop is therefore the next value in sorted order, and k -= 1 on the pop counts ranks exactly. Counting on the push instead would count nodes from the root down, which is not sorted order.
Counting
k -= 1when a node is pushedLooping
while stackinstead ofwhile node or stackPushing
node.rightstraight ontostackWalking every node when the nearest values are already found
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Binary search tree" plus "the k-th smallest value": rank means position in sorted order, and in a BST the inorder walk (left subtree, node, right subtree) already produces sorted order. When a BST question is about ranks, neighbouring values or the values nearest a target, that is the signal for BST Inorder.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision is made at each pop: k -= 1, and if k == 0, node.val is the answer; otherwise node = node.right and the walk goes on. k always counts the visits still needed.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: count on the pop (
k -= 1afterstack.pop()), not on the push.kis 1-indexed: runk -= 1before thek == 0test. Testing first returns the (k + 1)-th smallest value.Return inside the loop at
k == 0. Finishing the walk and remembering the k-th value is still correct, but it visits all n nodes instead of stopping after k.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use BST Inorder. In a binary search tree, visiting the left subtree, then the node, then the right subtree hands out the values in sorted order, so the k-th smallest is simply the k-th visit. I walk iteratively with a stack: going left, I push every node I pass, so when I pop a node, everything smaller than it has already been visited. On each pop I decrement k, and when k reaches zero I return that node's value; otherwise I continue from its right child. The trap is where I count: nodes are pushed from the root down, so counting pushes would return a value near the root instead of the k-th smallest. Counting pops keeps the count equal to the rank. I stop after k visits, so the time is O(H plus k), where H is the height of the tree, and the stack uses O(H) space.
Complexity & Mathematical Proof
O(H + k)
Look at the code: before the first visit, the inner while node: loop pushes the left edge of the tree, at most H nodes. After that, each pass of the outer loop visits one node with stack.pop() and k -= 1, and every node pushed along the way is either visited later or still on stack when the function returns. The walk returns at the k-th visit, so it makes at most k pops and at most H + k pushes, each O(1). Total: O(H + k).
O(H) stack
Every node on stack is an ancestor of node whose left subtree is still being walked, so stack holds at most one root-to-leaf path: O(H) nodes. The answer is one integer.
Derivation Progression
at most H pushes
Before the first visit, while node: pushes the left edge of the tree, one node per level.
k pops
Each pass of while node or stack: pops one node and runs k -= 1; the function returns at the k-th pop.
at most H + k pushes in total
Every pushed node is either popped (at most k of them) or still on stack at the return (at most H).
O(H + k)
Each push and pop is O(1).
Variable Definitions
Number of nodes in the tree
Height of the tree: about log n when balanced, up to n on a chain
The rank asked for, 1 <= k <= n
Memory Architecture & Bounds
O(1): iterative, no recursion
O(H): stack holds one root-to-leaf path at most
O(1): one integer
Boundary Best / Worst Cases
: k = 1, one dive down the left edge and a single visit
on a balanced tree
: k = n, or a chain of height
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "binary search tree", "the k-th smallest value". A rank question on a BST: BST Inorder, read as a stream that stops after k visits.
nodes, . Copying every value into a list and sorting costs time and memory; the iterative walk stops after k visits, so it costs time and only the stack, where is the tree height ( when balanced, up to on a chain).
A chain of nodes is levels deep: a recursive walk can overflow a small call stack, and the explicit stack avoids that. LeetCode's follow-up (many queries while nodes are inserted and deleted) calls for storing each node's subtree size, so one query walks a single root-to-leaf path in .