The problem
Given a binary search tree and k, return the k-th smallest value in it.
Input: [5, 3, 6, 2, 4, null, null, 1], k = 3 Output: 3
Picture it
In a search tree, smaller values are always to the left. So reading the tree “left side, then the node, then right side” (an inorder walk) visits values in sorted order, like reading library shelves from left to right. We do that walk with a stack and stop at the k-th value.
How to recognise it
- The tree is a binary search tree (BST): smaller values on the left, bigger on the right.
- The question is about rank ("k-th smallest"), and an in-order traversal of a BST (left, node, right) visits values in sorted order.
- So the answer is the k-th node of the in-order traversal, and you can stop as soon as you reach it.
- Up to 10^4 nodes and 1 ≤ k ≤ n.
Start with brute force
Ignore the BST order: collect every value, sort, and pick position k − 1.
def kth_brute(root, k):
vals = []
def walk(node):
if node:
vals.append(node.val)
walk(node.left)
walk(node.right)
walk(root)
return sorted(vals)[k - 1]
It is O(n log n) time and O(n) space: about 1.3 × 10^5 steps for 10^4 nodes, which passes. But it sorts values the tree already keeps in order, and it reads the whole tree even when k = 1. A recursive in-order walk into a list is already sorted, which removes the sort but not the full walk.
From brute force to the idea
- Find the waste. The sort repeats work the BST already did, and the walk continues long after the k-th value has gone by.
- Walk in order. In-order traversal of a BST gives the values from smallest to largest, so count nodes as you visit them.
- Use your own stack. To be able to stop in the middle, the shown code keeps an explicit stack.
while node:slides down left children, pushing each; the top of the stack is then the smallest unvisited value. - Visit, count, move right. Pop a node, decrease
k. Ifkreaches 0, this is the answer. Otherwise go to the node's right child, whose subtree holds the next values in order.
This is the key idea: an in-order walk of a BST is sorted, so stop after k visits.
The key idea
Inorder traversal of a BST is sorted; stop after k visits. O(height + k).
Python solution
def kth_smallest(root, k):
stack, node = [], root
while stack or node:
while node: # slide down to the smallest
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.rightIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (collect and sort) | O(n log n): the sort dominates | O(n): every value in a list |
| Iterative in-order (shown code) | O(h + k): slide down h levels, then visit k nodes | O(h): the stack holds at most one root-to-node path |
Here h is the height: about 14 for a balanced tree of 10^4 nodes, up to n for a chain.
Edge cases
- k = 1: the leftmost node, found after the first slide down.
- k = n: the largest value; the whole tree is visited.
- Single node, k = 1: returns that value.
- k larger than the number of nodes, or k = 0: the loop ends without a match and the function returns
None(no exception). LeetCode guarantees 1 ≤ k ≤ n. - Very deep tree: a chain of 10^4 nodes works, because the stack is a Python list and no recursion is used.
Common mistakes
- Checking
k == 0before decreasing it, which returns the (k + 1)-th value. - Forgetting
node = node.right: the popped node is pushed straight back and popped again, so the function returns the smallest value for every k. - Using preorder or level order: those are not sorted, even in a BST.
- Sorting the values, which works but throws away the BST property.
Return the k-th largest value in a BST. For [5, 3, 6, 2, 4, null, null, 1] and k = 2 the answer is 5. Describe your approach, then write it if you like.
Compare with our answer
Run the in-order walk backwards: right, node, left. That visits values from largest to smallest, so the k-th visit is the answer. Swap every left and right in the shown code.
def kth_largest(root, k):
stack, node = [], root
while stack or node:
while node: # slide down to the largest
stack.append(node)
node = node.right
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.left
Time O(h + k), space O(h). Using the k-th smallest with rank n − k + 1 also works but first needs the size n, which costs a full walk.
A strong answer mentions: reverse in-order order, stopping after k visits, and why counting the size first is wasteful.
1. A BST holds 10^6 timestamps and you often need the 3rd earliest. Which approach fits best?
In-order visits a BST in sorted order, so it can stop after k nodes at O(h + k) cost. Sorting or keeping the smallest values reads everything, and BFS order is not sorted.
2. Why is the shown solution O(h + k) rather than O(n)?
Reaching the smallest value costs up to h pushes, and each later visit is amortised O(1); the loop returns on the k-th pop. It does visit right subtrees when they come next in order, and it stores no subtree counts.
3. In the shown code, what happens when k is larger than the number of nodes?
After the last node, both stack and node are empty, so the while loop ends and Python returns None. stack.pop() is never called on an empty stack, because the outer loop checks first.
Score 60% or more and the lesson is marked complete.