The problem
Given the root of a binary search tree and a number k, return the k-th smallest value in the tree (counting from 1).
Examples
01
- Input
root = [3, 1, 4, null, 2], k = 1
- Output
1
02
- Input
root = [5, 3, 6, 2, 4, null, null, 1], k = 3
- Output
3
Constraints
- 1 ≤ k ≤ number of nodes ≤ 10⁴
- 0 ≤ Node.val ≤ 10⁴
The idea
An in-order walk — left subtree, then the node, then the right subtree — visits a BST’s values in increasing order. So the k-th node it visits is the answer.
Walk it with an explicit stack, so the walk can stop the moment the count reaches k: go left as far as possible, pushing each node; pop one — the next smallest — count it; then turn to its right subtree and repeat.
- Time
- O(h + k) — down to the smallest, then k steps
- Space
- O(h) — the stack
Solution · every language run against every case
class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: # An in-order walk (left, node, right) visits a BST's values in increasing order. stack, node = [], root while True: while node: # go as far left as possible, remembering the way back stack.append(node) node = node.left node = stack.pop() k -= 1 if k == 0: return node.val node = node.right