You are given root, the root of a binary search tree whose values are all different, and two
different values p and q that are both in the tree.
Return the value of their lowest common ancestor: the deepest node that has both p and q
in its subtree. A node counts as part of its own subtree, so if p is above q, the answer is
p.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [20, 10, 30, 5, 15, 25, 35, null, null, 12, 18], p = 12, q = 5
- Output
- 10
Example 2
- Input
- root = [20, 10, 30, 5, 15, 25, 35, null, null, 12, 18], p = 15, q = 18
- Output
- 15
Constraints
- The tree holds 2 to 1000 nodes.
- Values are distinct, between −10⁴ and 10⁴.
p≠q, and both are values in the tree.
Show the pattern
Trees
The ordering tells you which side both values are on. While they are on the same side of a node, go that way; the first node that separates them, or is one of them, is the answer.
See trees in a visualiserShow the approach
Start at the root. If p and q are both smaller than the node's value, both are in the left
subtree, and so is their lowest common ancestor: go left. If both are larger, go right.
Otherwise the node separates them, or is one of them, so no deeper node has both below it:
return its value.
The walk follows a single path down, with no recursion and no extra memory.
Time: O(h), h the tree's height · Space: O(1)