The tree is a search tree with distinct keys: for every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write kth_lowest(root, k) -> int: the k-th smallest key in the tree, counting from 1.
# 8
# / \
# 3 12
# / \ \
# 1 6 15
kth_lowest(root, 1) # 1
kth_lowest(root, 3) # 6
kth_lowest(root, 6) # 15
- Up to 70,000 nodes, at most 500 levels deep. Keys are distinct integers between
-10^9and10^9. 1 <= k <=the number of nodes.- Aim for O(h + k), where
his the height of the tree: stop as soon as you know the answer. The tests count how many nodes you look at, so collecting every key first and then picking one is not enough.
Show hint
Visiting a search tree left subtree, node, right subtree hands you the keys in increasing order. Count as you go.