Kth Smallest Element in a BST
You get a binary search tree as the array root in heap order: the root is at index 0, the children of index i are at 2*i+1 (left) and 2*i+2 (right), and -1 marks an empty spot. The array may end with extra -1 entries. At every node, the left subtree holds only smaller values and the right subtree only larger ones.
Return the k-th smallest value in the tree, counting from 1.
Function
- rootinteger-array
- the binary search tree in level order, with -1 for an empty spot
- kinteger
- the position to find in increasing order, starting at 1
- Returnsinteger
- the k-th smallest value in the tree
Constraints
1 ≤ root.length ≤ 32767- Each
root[i]is-1or a value with0 ≤ root[i] ≤ 105. root[0]is never-1, so the tree has at least one node.- The array may end with extra
-1entries past the last node. - Both children of an empty spot are empty too, and the depth is at most
14. - The ordering rule holds at every node, so no value appears twice.
1 ≤ k ≤the number of nodes in the tree.
Examples
- Input
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Output
- 29
- Explanation
- In increasing order the values are
6, 17, 22, 29, 41, 65, 90, and the fourth is29. It is the largest of the four values in the root's left subtree.
- Input
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Output
- 2
- Explanation
- The smallest value ends the path that keeps going left:
12,5,2. The7under9and the-1padding do not change that.
Follow-up
If the tree changes often and you are asked for the k-th smallest value many times, what could each node store so that every query takes O(h)?
Hints
Open them one at a time. Each one gives away a little more.
Which way of walking a binary search tree lists its values from smallest to largest?
Visiting the left subtree, then the node, then the right subtree gives sorted order. The
k-th value that walk produces is the answer, so you can stop there.Use a stack. From the current node, push nodes while moving to the left child. Pop the top and count it; stop at the
k-th pop. Otherwise move to the popped node's right child at2*i+2and repeat.
Solution
An in-order walk (left subtree, node, right subtree) reads a binary search tree's values in increasing order, so the k-th value it reaches is the answer. Run the walk with your own stack and stop there; no sort is needed.
Collect every value and sort
Intuition
Ignore the shape: keep every entry that is not -1, sort, and return position k-1. For the first example the sorted list is 6, 17, 22, 29, 41, 65, 90, and position 3 holds 29.
It is correct for any tree, ordered or not. That is also its cost: it ignores the order the tree already has, and pays O(n log n) for the sort and O(n) memory for the copy.
Algorithm
- Collect every entry of
rootthat is not-1. - Sort the collected values in increasing order.
- Return the value at position
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]In-order traversal into a list
Intuition
Below any node, the left subtree holds only smaller values and the right subtree only larger ones. Visit the left subtree, then the node, then the right subtree, and do the same inside each subtree: every node lands after all smaller values and before all larger ones, so the output is sorted. In the first example the walk yields 6, 17, 22, 29, 41, 65, 90.
One pass replaces the sort: O(n) time, and O(n) space for the list. It still visits the whole tree, even for k = 1, where the answer ends the leftmost path.
Algorithm
- Write
inorder(i): return at an empty spot (past the end or-1). - Otherwise call
inorder(2*i+1), appendroot[i]to the list, then callinorder(2*i+2). - Call
inorder(0). - Return the list entry at position
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedIterative in-order that stops at k
Intuition
An explicit stack lets you stop the walk in the middle. Go left as far as you can, pushing each node. The node on top is the smallest value not counted yet, because everything smaller sits in its left subtree, which is empty or already counted. Pop and count it; its right subtree comes next in sorted order.
For k = 4 in the first example: push 41, 17, 6. Pop 6, then 17, and move to its right child: push 29 and 22. Pop 22, then 29, the fourth. The walk never touches 65 or 90.
The stack holds at most one node per level, so the space is O(h). The walk goes down once and then pops k times: O(h + k) time.
Algorithm
- Start with an empty stack and
i = 0. - While
iis a real node, push it and move to2*i+1. - Pop the top into
iand subtract1fromk. - If
kis now0, returnroot[i]. - Otherwise move to
2*i+2and go back to step 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
Pitfalls and edge cases
- Reading the array in index order. Level order is not sorted: the first example starts
41, 17, 65. - Off by one on
k. It counts from1: return list positionk-1, and stop the walk when the count reachesk. - Skipping the right subtree after a pop. In the second example
9and7sit in the right subtree of5, and the walk would never count them. - Treating a missing child as real. A child is empty when its index is past the end or holds
-1:22sits at index9, so its children19and20are past the end. - Lua and R arrays start at 1. Keep node indexes 0-based for
2*i+1and readroot[i + 1].
Frequently asked questions3
What is the time complexity of finding the kth smallest element in a BST?
The iterative in-order walk takes O(h + k) time and O(h) extra space for a tree of depth h. In the worst case, k = n or a tree shaped like a path, that is O(n).
How do you find the kth largest element in a BST?
Mirror the walk: right subtree, then the node, then the left subtree. That lists the values in decreasing order. Go right as far as you can while pushing, pop and count, and move to the left child after each pop. The k-th pop is the k-th largest.
How do you stop a recursive in-order traversal at the k-th value?
Keep a counter outside the recursion, starting at k. Subtract 1 after a node's left subtree returns, and record the node's value when the counter reaches 0. After every call, return at once if the answer is recorded. The recursion then matches the stack version: O(h + k) time, O(h) space.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def kthSmallest(root, k):
# Write code hereTest #1
Test #2
Arguments
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Expected Output
29