Given a binary tree and two values p and q (both present), return the value of their
lowest common ancestor — the deepest node that has both p and q somewhere below
it (a node is an ancestor of itself).
lowestCommonAncestor(root, p, q)
Input format: tree | p | q (level-order tree with x for missing children).
(3 5 1 6 2 0 8), p=5, q=1 // → 3
(3 5 1 6 2 0 8), p=6, q=2 // → 5
(3 5 1 6 2 0 8), p=5, q=2 // → 5
The LCA of two nodes is the deepest single point in the tree from which both are reachable. One brute-force idea: find the root-to-node path for each target separately, then compare where the paths last agree. That works, but needs two full traversals, extra storage, and a comparison pass.
Instead, ask at every node: does this subtree contain p, q, or both? The LCA is the one node where the search paths to p and q are still together, right before they'd split into different subtrees.
DFS from any node: if the node itself is p or q, report "found" upward immediately — a node counts as its own ancestor. Otherwise recurse into both children, then look at what came back:
Every node is visited once at constant cost. The moment both children report a hit is guaranteed to be the lowest such point, since the search works bottom-up — any convergence higher up would only be reached after this lower one is already found and passed along. O(n) time, O(h) space for the recursion stack — much cheaper than materializing two full paths and comparing them.
def lowest_common_ancestor(root, p, q):
def find(node):
if node is None:
return None
if node.val == p or node.val == q:
return node
l = find(node.left)
r = find(node.right)
if l is not None and r is not None:
return node
return l if l is not None else r
return find(root).val
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.