Lowest Common Ancestor of a BST

Given a BST and two node values p and q known to exist in the tree, return the value of their lowest common ancestor.

Example

Input tree: 6 2 8 0 4 7 9 null null 3 5, p = 2, q = 8 Output: 6

Approach

The BST ordering property does the work for you: starting at the root, if both p and q are smaller, the answer must be in the left subtree; if both are larger, it must be in the right subtree; the moment they split (one is on each side, or one equals the current node), the current node is the lowest common ancestor — no need to search both subtrees like you would in a general tree.

Input format

Line 1: the tree in level-order, space-separated, null for missing children Line 2: p q

Print the LCA's value.