889. Lowest Common Ancestor in BST

Given the root of a binary search tree and two keys p and q (both present), return the value of their lowest common ancestor. Exploit the BST property: the LCA is the first node from the root where p and q split to different sides (or equals one of them). The input gives a level-order BST array and 'p q' separated by ' | '.

Input: A level-order BST array and 'p q', separated by ' | '.

Output: Integer — the LCA key.

Examples

Input: [8,3,10,1,6,null,14] | 1 14
Output: 8
Explanation: Keys 1 and 14 split at the root.

Input: [4,2,7,1,3] | 1 3
Output: 2
Explanation: 2 is the lowest common ancestor of 1 and 3.

Input: [2,1,3] | 1 3
Output: 2
Explanation: The root is the LCA.

Constraints

• 2<=nodes<=10^4
• valid BST
• p and q present

Asked by