K-th Fastest Finisher
At a city marathon, each finishing time in seconds is inserted into a binary search tree as the runner crosses the line: faster times go left, slower times go right. The tree is never re-sorted, so its shape depends on who finished when.
The prize table wants to call up runners by place: the 3rd fastest, then the 10th fastest for a random spot prize. You are given the tree and a place k. The tree already keeps the times in order, so there should be no need to copy them all out and sort them.
Your task
Write kthFastest(root, k). root is a valid binary search tree. Return the k-th smallest value in it, where k = 1 means the smallest.
All times are different, and k is always between 1 and the number of nodes. Trees are shown in level order, like [9000, 8000, 9500], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
kthFastest(root: TreeNode, k: int) → int
Examples
root = [9000, 8000, 9500, 7800, 8600, 9200, 9900] k = 3
8600
In order, the times are 7800, 8000, 8600, 9000, 9200, 9500, 9900. The 3rd is 8600. Reading the tree level by level would give 9000, 8000, 9500, so the 3rd value in the tree layout (9500) is the wrong answer.
root = [9000, 8000, 9500, 7800, 8600, 9200, 9900] k = 7
9900
With 7 runners, place 7 is the slowest: the rightmost node. Places count from 1, so k = 7 is the last, not past the end.
Constraints
- 1 ≤ number of runners ≤ 1,000
- 1 ≤ k ≤ number of runners
- 1 ≤ time ≤ 86,400, all different
- The tree is a valid binary search tree, at most 500 levels deep.
Start with brute force
Collect every time into a list, sort it, and return the item at position k - 1. That is O(n log n) and it always visits all n runners, even when you only want the fastest.
The sort is wasted work: a binary search tree already stores the times in order, you just have to read them in the right order. An in-order walk lists them sorted for free and can stop after k of them.
Hints
0 of 4 shown- Hint 1
In a search tree, where is the fastest time of all? And which time comes right after it?
- Hint 2
Visiting the left subtree, then the node, then the right subtree visits the values from smallest to largest. That order is called in-order.
- Hint 3
So the answer is the k-th node an in-order walk visits. Do you need to finish the walk once you have counted to k?
- Hint 4
Do an in-order walk with a counter (recursively, or with an explicit stack: push nodes while going left, pop one, count it, then go to its right child). When the counter reaches k, return that node's value and stop.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
In a binary search tree, everything left of a node is smaller and everything right is larger. So "left subtree, node, right subtree" visits the values in sorted order. Count as you visit and stop at k.
Trace [9000, 8000, 9500, 7800, 8600, 9200, 9900] with k = 3:
- Slide left from 9000: push 9000, 8000, 7800.
- Pop 7800. Count 1. It has no right child.
- Pop 8000. Count 2. Go to its right child 8600 and slide left: push 8600.
- Pop 8600. Count 3. That is
k, so return 8600.
The walk never touched 9500, 9200 or 9900. The explicit stack does what the recursion stack would do, but makes it easy to stop the moment the count reaches k.
function kthFastest(root, k) {
const stack = [];
let node = root;
while (true) {
while (node !== null) { // slide to the smallest unvisited time
stack.push(node);
node = node.left;
}
node = stack.pop(); // next time in sorted order
k -= 1;
if (k === 0) return node.val;
node = node.right; // then the times just above it
}
}def kth_fastest(root, k):
stack = []
node = root
while True:
while node is not None: # slide to the smallest unvisited time
stack.append(node)
node = node.left
node = stack.pop() # next time in sorted order
k -= 1
if k == 0:
return node.val
node = node.right # then the times just above itRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.