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 treeroot = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8Output6WhyThe two values lie in different subtrees of node 6, so 6 is their lowest common ancestor.root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4Output2WhyNode 2 is an ancestor of 4, and a node can be its own ancestor.root = [2,1], p = 2, q = 1Output2WhyThe root is one of the target nodes, so it is the lowest common ancestor.2 <= number of nodes <= 10^5-10^9 <= node.val, p, q <= 10^9All BST node values are uniquep and q are guaranteed to exist in the treedef lowest_common_ancestor_bst(root, p, q):
