Lowest Common Ancestor of a Binary Search Tree
MediumTrees
You are given the root of a binary search tree and two different nodes of that tree, p and q. Return their *lowest common ancestor*: the deepest node that has both p and q in its subtree.
- A node counts as being in its own subtree, so if
pis an ancestor ofq, the answer ispitself. - 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. All values are distinct.
p and q are passed as TreeNode objects from the tree; the examples identify them by value, and the answer is shown as the value of the node you return.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [20,10,30,5,15,25,35,null,null,12,18], p = 5, q = 18
- Output:
- 10
- Explanation
- Both values are below 20, so the answer is in the left subtree. At 10, 5 goes left and 18 goes right, so the paths split here and 10 is the answer.
Example 2
- Input:
- root = [20,10,30,5,15,25,35,null,null,12,18], p = 15, q = 18
- Output:
- 15
- Explanation
- 18 is a child of 15, and a node counts as its own ancestor, so the answer is 15 itself.
Example 3
- Input:
- root = [20,10,30,5,15,25,35,null,null,12,18], p = 12, q = 35
- Output:
- 20
- Explanation
- 12 is smaller than the root and 35 is larger, so they are on opposite sides of 20 and the root is the lowest common ancestor.
Constraints
- The number of nodes is in the range
[2, 10^5] -10^9 <= Node.val <= 10^9- All values are distinct
p != q, and bothpandqare nodes in the tree