Lowest Common Ancestor in a BST

You get the root of a binary search tree (BST). You also get two values, p and q, that are both in the tree. Return the value of their lowest common ancestor.

That is the deepest node with both p and q in its subtree. A node counts as part of its own subtree. So if p is above q, the answer is p.

In a BST, every value in a node's left subtree is smaller than the node's value. Every value in its right subtree is larger.

Trees are written level by level, from top to bottom and left to right. A None marks a missing child.

Example 1:

        8
       / \
      3   12
         /  \
       10    15
      /  \
     9    11

Input: root = [8,3,12,None,None,10,15,9,11], p = 9, q = 15
Output: 12
Explanation: 9 is in the left subtree of 12.
15 is in its right subtree.
No deeper node has both of them below it.

Example 2:

Input: root = [8,3,12,None,None,10,15,9,11], p = 11, q = 12
Output: 12
Explanation: 11 is below 12.
12 is part of its own subtree, so the answer is 12 itself.

Example 3:

Input: root = [0,-4,6], p = 6, q = 6
Output: 6
Explanation: p and q can be the same value.
Then the answer is that node.

Constraints:

• 1 to 15 nodes.
• Each value is a whole number from -100 to 100.
• No two nodes have the same value.
• p and q are values in the tree. They can be equal.