Kth Smallest Element in BST
Kth Smallest Element in a BST is LeetCode 230 (Medium). You get the root of a binary search tree and an integer k. Return the k-th smallest value among all its nodes, counting from 1.
- In a binary search tree (BST), every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger.
- The tree has
nnodes, with1 ≤ k ≤ n ≤ 10⁴and values from 0 to 10⁴. - Follow-up: what if the tree changes often and the k-th smallest is asked for many times?
- The number of nodes in the tree is n.
- 1 <= k <= n <= 10⁴
- 0 <= Node.val <= 10⁴
Intuition
An inorder traversal visits a node's left subtree, then the node, then its right subtree. In a BST that means smaller values, then the node, then larger values, so inorder reads the values in ascending order.
The kth smallest element in BST is therefore the k-th node that inorder visits. Count the visits and stop at the k-th; the rest of the tree is never touched.
An explicit stack makes stopping easy. Nodes waiting for their turn sit on the stack, and each pop hands back the next smallest value.
A question about order in a BST, such as the k-th smallest value, the next larger value, or whether the tree is valid, is an inorder traversal with a check in place of printing. Besides this kth smallest element in a BST LeetCode problem, Validate Binary Search Tree (98), Binary Search Tree Iterator (173) and Minimum Absolute Difference in BST (530) use the same stack loop.
Approach
Before reading on, list the values of [5,3,6,2,4,null,null,1] in ascending order without sorting, just by walking the tree. Which nodes did you pass before writing down the first value?
Two ways to solve it
Walk left pushing nodes, pop the next smallest, count it, then turn right.
- Stopping: a plain
returnat the k-th pop. - Depth: no recursion limit on a long chain.
- Reuse: the same loop is a BST iterator.
The version most solutions show.
Recurse left, count the node, recurse right, and pass the answer back up once found.
- Stopping: every call must check whether the answer came back.
- Depth: one call per level of the tree.
- Reads like: the definition of inorder.
Same cost, a little more care to stop early.
Both visit the same nodes in the same order, but the stack version can simply return at the k-th pop. The steps, code and live demo below follow the stack version; the recursive code comes after the demo.
Walk left, stacking the path
From the current node, push it and move to its left child, until there is no left child. Every pushed node is still waiting, because its smaller values on the left come first. The top of the stack is now the smallest value not yet visited.
Pop the next smallest and count it
Pop the top node; it is the next value in ascending order. Decrease k by one, and if k reaches 0, return this node's value. In the kth smallest element in a BST Python code, the stack is a plain list, so append pushes and pop takes the top.
Move to the right subtree
Everything smaller than the popped node is done, so the next larger values are in its right subtree. Set node = node.right and go back to walking left. If there is no right child, the next pop returns the nearest ancestor still waiting.
Follow-up: a tree that changes often
Store in each node the size of its left subtree, L. To find the k-th smallest, start at the root:
k <= L: go left.k == L + 1: this node is the answer.k > L + 1: go right withk − L − 1.
Each query is O(h); an insert or delete updates the sizes along its path.
Kth Smallest Element in BST solution in Python | C++ | Java
k drops to 2 and the walk goes on. It has no right child, so the next pop returns 2, the nearest ancestor still waiting.k drops to 1 and the walk goes on. It has no right child, so the next pop returns 3, the nearest ancestor still waiting.k drops to 4 and the walk goes on. It has no right child, so the next pop returns 3, the nearest ancestor still waiting.k drops to 3 and the walk goes on. The next larger values are in its right subtree, so node moves to 6.k drops to 2 and the walk goes on. It has no right child, so the next pop returns 6, the nearest ancestor still waiting.k drops to 1 and the walk goes on. The next larger values are in its right subtree, so node moves to 7.Recursive inorder with a counter
inorder searches the left subtree first and passes back its answer if it found one. Otherwise it counts the current node, returns its value when the count reaches k, and searches the right subtree.
Common pitfalls
Collecting every value before answering
vals = []
def dfs(n):
if n:
dfs(n.left)
vals.append(n.val)
dfs(n.right)
dfs(root)
return vals[k - 1]node = stack.pop()
k -= 1
if k == 0:
return node.valIt gives the right answer, but it visits all n nodes and stores n values when the answer is known after k visits. Stopping at the k-th pop costs O(h + k).
Counting a node when it is pushed
while node:
stack.append(node)
k -= 1
node = node.leftnode = stack.pop()
k -= 1
if k == 0:
return node.valNodes are pushed on the way down the left side, largest first, long before their turn. A node takes its place in sorted order only when it comes off the stack.
Going left after a pop
node = stack.pop() ... node = node.left
node = stack.pop() ... node = node.right
The popped node's left subtree is already finished; that is why it was popped. Going left again repeats those nodes forever. The unvisited, larger values are on the right.
Complexity
Kth Smallest Element in BST FAQ
How do you find the kth largest element in a BST?
Mirror the walk: go right first, then the node, then left. That visits the values in descending order, so the k-th pop is the k-th largest.
Can the kth smallest element in a BST be found with O(1) extra space?
Yes, with Morris traversal. Before going left, it links the rightmost node of the left subtree back to the current node, so the walk can climb back up without a stack, and it removes each link on the way back. Count the visits exactly as above and stop at the k-th. Time is O(n), extra space O(1), and the tree is restored.