Example 1
ready- Input
root = [ 3, 5, 1, 6, 2, 0, 8, null, null, 7, 4 ] p = 5 q = 1- Expected
3- Why
- 5 and 1 first meet at the root value 3
Lowest Common Ancestor
35 min · lowestCommonAncestor()mediumOpen in LeetCode #236 ↗
Two people in a family tree can share many ancestors. The answer you want is the shared one closest to them, not the oldest name at the top.
You're given a binary tree whose node values are unique, plus two different values p
and q that both occur in the tree. Return the value of their lowest common ancestor
(LCA): the deepest node whose subtree contains both targets.
A node belongs to its own subtree. That means when p is an ancestor of q, the answer
is p itself, and the same rule works in the other direction.
A few ground rules:
- This is a general binary tree, not necessarily a binary search tree.
- You receive target values rather than node references, and you return the ancestor's integer value.
- The tree is displayed as a level-order array, with
nullmarking a missing child.
Constraints
2 <= node count <= 10_000- All node values are unique.
-2_147_483_648 <= node.val <= 2_147_483_647p != q- Both
pandqare present in the tree.
Hints
Trace both routes
First find the path of values from the root to p, then the path from the root to
q. Where do those two paths stop agreeing?
Ask each subtree what it found
In a recursive search, a subtree can report p, report q, report an ancestor
already found below it, or report nothing.
One target on each side
When the left and right recursive calls both report a node, the current node is the first place where the two targets meet. Return it upward unchanged.
Follow-up
How would you preprocess a tree once so you could answer a large stream of LCA queries without scanning the whole tree every time?
Visible cases
Examples
Example 2
ready- Input
root = [ 3, 5, 1, 6, 2, 0, 8, null, null, 7, 4 ] p = 5 q = 4- Expected
5- Why
- a target can be the ancestor: 5 already contains 4 below it
Example 3
ready- Input
root = [ 1, 2, null, 3 ] p = 2 q = 3- Expected
2- Why
- 2 lies directly on the path from the root to 3
Interview signal
Asked at
AmazonMetaMicrosoft
Compare root paths
Find the route from the root to each target. The two routes share a prefix; the final value in that shared prefix is the lowest common ancestor.
def lowest_common_ancestor(root: TreeNode | None, p: int, q: int) -> int:
def find_path(node: TreeNode | None, target: int, path: list[int]) -> bool:
if node is None:
return False
path.append(node.val)
if node.val == target:
return True
if find_path(node.left, target, path) or find_path(node.right, target, path):
return True
path.pop()
return False
p_path: list[int] = []
q_path: list[int] = []
find_path(root, p, p_path)
find_path(root, q, q_path)
answer = p_path[0]
for p_value, q_value in zip(p_path, q_path):
if p_value != q_value:
break
answer = p_value
return answerIf one target is an ancestor of the other, its path ends while the longer path keeps going. The last matched value is still the right answer.
Time O(n) — the two searches visit at most 2n nodes. Space O(h) for the paths
and recursive stack, where h is the tree's height.
One post-order search
A post-order search asks the children before deciding what the current node means. Return the current node immediately when it matches a target. Otherwise, search both subtrees:
- If both sides return a node, one target was found on each side, so the current node is their LCA.
- If only one side returns a node, pass that result upward.
- If neither side returns a node, pass
Noneupward.
def lowest_common_ancestor(root: TreeNode | None, p: int, q: int) -> int:
def search(node: TreeNode | None) -> TreeNode | None:
if node is None or node.val == p or node.val == q:
return node
left = search(node.left)
right = search(node.right)
if left is not None and right is not None:
return node
return left if left is not None else right
ancestor = search(root)
if ancestor is None:
raise ValueError("targets are missing")
return ancestor.valThe "target is its own ancestor" rule falls out naturally: finding p returns that node
without needing to prove where q sits below it. The input guarantee supplies that
proof.
Time O(n) — each node is visited at most once. Space O(h) for the recursive stack.
LeetCode passes and returns TreeNode references; ours passes the two target values and returns the ancestor's value so the judge can compare it.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite