Implement lowest_common_ancestor(level_order, p, q) for a binary search tree with unique integer values. Return the integer value of the deepest node whose subtree contains both target nodes. A node belongs to its own subtree, so either target can be the answer.
level_order encodes the tree in breadth-first order. Its first value is the root. For each non-null node, consume its next left and right child entries; null entries have no children. Omitted trailing children are null. Examples use null for an absent child.
The input is a valid BST with 2 through 100,000 nodes. Values are between -1,000,000,000 and 1,000,000,000. The distinct values p and q both exist. Every left-subtree value is smaller than its ancestor; every right-subtree value is larger.
Examples
lowest_common_ancestor([6,2,8,0,4,7,9,null,null,3,5], 2, 8) -> 6
lowest_common_ancestor([6,2,8,0,4,7,9,null,null,3,5], 2, 4) -> 2
The second result is a target node because its subtree also contains the other target. Return a value rather than a tree-node object; uniqueness makes the answer unambiguous.
Problem reference: LeetCode 235.