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.
For two keys p and q that are both in the tree, their meeting point is the deepest node whose subtree contains both of them. A node counts as part of its own subtree, so if p sits above q, the meeting point is p itself.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write meeting_points(root, pairs) -> list[int]: for every [p, q] in pairs, the key of their meeting point, in the same order as pairs.
# 20
# / \
# 10 30
# / \ / \
# 5 15 25 40
# / \
# 12 18
meeting_points(root, [[5, 15], [12, 18], [12, 40], [10, 12], [25, 25]])
# [10, 15, 20, 10, 25]
- Up to 70,000 nodes, and the tree is at most 50 levels deep. Keys are distinct, between
-10^9and10^9. - Up to 50,000 pairs. Both keys of every pair are in the tree;
pmay equalq, and they can come in either order. - Aim for O(h) per pair, where
his the height of the tree, with no extra memory. Searching the whole tree for every pair is too slow.
Show hint
Start at the root and compare both keys with the current node. As long as they fall on the same side, you know which way to go.