You are given the root of a binary search tree and an integer k. Return the kth smallest value stored in the tree, counting from 1. The tree is a valid BST, so every left subtree holds smaller values and every right subtree holds larger values.
- The number of nodes is n
- 1 <= k <= n <= 10^4
- 0 <= Node.val <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force collects every value, sorts them and picks index k - 1, which costs O(n log n) and O(n) space. But an inorder traversal (left, node, right) of a BST already produces the values in increasing order. So we only need to walk inorder and count: the kth node we visit is the answer, and we can stop right there without touching the rest of the tree.
Algorithm
- Start with an empty stack and
cur = root. - Push
curand move left untilcuris null. - Pop a node: this is the next smallest value. Decrease
k. - If
kbecomes 0, return this node's value. - Otherwise move to the popped node's right child and repeat.
O(h + k), where h is the tree heightSpace: O(h) for the stackk with the left subtree size.class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: stack = [] cur = root while cur or stack: # Go as far left as possible while cur: stack.append(cur) cur = cur.left cur = stack.pop() # next smallest value k -= 1 if k == 0: return cur.val cur = cur.right return -1