Lowest Common Ancestor of a Binary Search Tree

Medium

Given a binary search tree and two node values p and q present in it, return the value of their lowest common ancestor — the deepest node that has both as descendants (a node can be a descendant of itself).

Example 1

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

Example 2

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

Constraints

• 2 <= number of nodes <= 10^5
• All node values are unique.
• p and q exist in the BST.