A binary search tree (BST) is built from an empty tree by inserting the given keys one at a time, in the order they appear (go left for smaller keys, right for larger, dropping the key at the first empty spot). All keys are distinct.\n\nGiven two keys a and b that are both present in the tree, report the key stored at their lowest common ancestor (LCA): the deepest node that has both a and b in its subtree (a node is considered an ancestor of itself).\n\n## Input format\n\nLine 1: an integer n.\nLine 2: n distinct space-separated integers giving the insertion order.\nLine 3: two integers a and b, each guaranteed to be one of the inserted keys.\n\n## Output format\n\nA single integer: the key at the lowest common ancestor of a and b.\n\n## Constraints\n\n- 2 <= n <= 100000\n- -1000000000 <= each key <= 1000000000, and all keys are distinct.\n- a and b are distinct and both appear among the inserted keys.
Example 1
Input
6 8 3 10 1 6 14 1 6
Expected
3
Explanation
The tree has root 8; 3 is its left child with children 1 and 6. Both 1 and 6 sit under 3, and neither is an ancestor of the other, so their lowest common ancestor is the node with key 3.
Example 2
Input
5 5 2 9 1 3 1 3
Expected
2
Explanation
Root 5 has left child 2, whose children are 1 and 3. The deepest node containing both 1 and 3 in its subtree is 2, so the answer is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →