At Stripe, a service stores hierarchical configuration values in a binary search tree (BST). Given the root of a BST and two node values p and q that are guaranteed to exist in the tree, return the value of their lowest common ancestor (LCA).
The lowest common ancestor of two nodes is the deepest node that has both nodes as descendants, where a node can be a descendant of itself.
Implement a function that takes:
root: a BST represented as a nested object with keys val, left, and right, or nullp: integer value of the first nodeq: integer value of the second nodeReturn:
p and qExample 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 2 is in the left subtree of 6 and 8 is in the right subtree, so 6 is the first node where their paths split.
Example 2
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: A node can be its own ancestor, and 2 is an ancestor of 4.
2 and 10^5 nodes-10^9 <= node.val, p, q <= 10^9p and q are guaranteed to exist in the tree