In a binary search tree (BST), the left subtree of a node holds only smaller values, and the right subtree holds only larger values.
You are given a BST and two values p and q that exist in it. Find their lowest common ancestor (LCA): the lowest node that has both p and q somewhere below it. A node counts as being below itself. Return the value of that node.
How the judge passes the data
Examples
Example 1:
Input: root = [50,30,70,20,40,60,80,null,25,null,45], p = 25, q = 45
Output: 30
Explanation: The path to 25 and the path to 45 split at node 30. The lowest shared ancestor is 30.
Example 2:
Input: root = [50,30,70,20,40,60,80,null,25,null,45], p = 60, q = 80
Output: 70
Explanation: Both 60 and 80 are below 70, and 70 is the lowest such node.
Example 3:
Input: root = [50,30,70,20,40,60,80,null,25,null,45], p = 20, q = 25
Output: 20
Explanation: 25 is below 20, and a node counts as being below itself. So the answer is 20.