Binary Search Trees Using the ordering
389. Lowest Common Ancestor of a Binary Search Tree
You are given root, the root node of a binary search tree, and two of its nodes, p and q. Return their
lowest common ancestor.
In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every
value in its right subtree is larger. The values in the tree are distinct. The lowest common ancestor of
p and q is the deepest node that has both of them in its subtree. A node counts as part of its own
subtree, so when p is an ancestor of q, the answer is p itself.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out. p and q are written as the values they hold, and the
output shows the value of the node you return.
Example 1
Input: root = [40, 20, 60, 10, 30, 50, 70, null, 15, 25, 35]
p = 15
q = 35
20Explanation: 15 is in the left subtree of 20, under 10, and 35 is in its right subtree, under 30. No deeper node has both below it.
Example 2
Input: root = [40, 20, 60, 10, 30, 50, 70, null, 15, 25, 35]
p = 30
q = 25
30Explanation: 25 is the left child of 30. A node counts as part of its own subtree, so 30 is the answer.
Example 3
Input: root = [-5, -1000000000, 1000000000]
p = 1000000000
q = -1000000000
-5Explanation: p is the right child of the root and q the left child, so only the root has both below it.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
2 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
- The tree is a binary search tree, and its values are distinct.
pandqare different nodes of the tree.
Clarifying questions
What you would ask an interviewer before writing any code.