Where Two Search Paths Split

In a binary search tree with distinct values, the searches for two stored values a and b follow the same path from the root until they part ways. Return the value of the deepest node shared by both search paths (their lowest common ancestor). A node counts as its own ancestor, so if a lies above b the answer is a.

Examples

         12
        /  \
       7    18
      / \   / \
     3   9 15  22
      \
       5

Input:  root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), a = 3, b = 9
Output: 7

Input:  root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), a = 5, b = 22
Output: 12

Input:  root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), a = 7, b = 5
Output: 7

Constraints

• 1 <= number of nodes <= 3000
• Values are distinct and both a and b are in the tree
• O(h) time, O(1) extra space

Goals

• Use the ordering rule to locate the split point in O(h)
• Handle the case where one value is an ancestor of the other