Lowest Common Ancestor in a BST

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7. All trees in this topic that are called BSTs have different values.

Return the lowest common ancestor of the values p and q: the lowest node that has both in its subtree (a node counts as being in its own subtree). Both values are in the tree. The tests check the value of the node you return.

For [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], p = 2 and q = 8 the answer is the node 6; for p = 2 and q = 4 it is the node 2.

Examples

Example 1

Input:

lca_bst(root, 2, 8)  # root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]

Output:

6

Example 2

Input:

lca_bst(root, 2, 4)  # root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]

Output:

2

Constraints

• 2 <= number of nodes <= 100000
• The tree is a BST, not deeper than 800 levels.
• p and q are values in the tree.