Algorithm

Lowest Common Ancestor

Trees Pattern

Lowest Common Ancestor

Given the root of a binary tree and two nodes p and q that are both present in it, return their lowest common ancestor: the deepest node that has both p and q somewhere in its subtree. A node counts as a descendant of itself, so if p happens to be an ancestor of q, the answer is p. Return the node itself, not its value. This is an ordinary binary tree — no search-tree ordering may be assumed.

CONSTRAINTS
  • The number of nodes in the tree is in the range [2, 10⁵]
  • -10⁹ <= Node.val <= 10⁹, and all values are unique
  • p and q are distinct and both exist in the tree
  • A node is considered a descendant of itself
EXAMPLE 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
5 sits in the root's left subtree and 1 in its right, so the root is the only node containing both. Any node below the root is missing at least one of them.
EXAMPLE 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
4 lies beneath 5, and because a node counts as its own descendant, 5 itself qualifies as an ancestor of both. Answering 3 would be a common ancestor, just not the lowest one.
EXAMPLE 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 7, q = 4
Output: 2
7 and 4 are the two children of 2, so their paths from the root diverge exactly there. Everything above 2 also contains both, but sits higher.
EXAMPLE 4
Input: root = [1,2], p = 1, q = 2
Output: 1
The root is one of the two targets and contains the other, so it is the answer — the same self-ancestor rule, at the top of the tree.
Can a node be its own ancestor?
Yes, and this rule decides several cases. If p is an ancestor of q, the answer is p rather than p's parent.
Is this a binary search tree?
No, so you cannot compare values to choose a direction. If it were a BST, the ordering would let you walk down from the root without any recursion at all — a much cheaper variant worth mentioning.
Are p and q guaranteed to exist?
Yes here. That guarantee is load-bearing: the standard solution returns a node even when only one target is present, so a version without the guarantee would need a second pass or a count to verify both were actually found.
Should I compare nodes by value or by reference?
By reference, since you are given the node objects. Values are unique here so either works, but with duplicates only reference comparison is well defined.

The lowest common ancestor of two nodes is the deepest node that still has both of them somewhere below it.

Picture it. Say p = 7 and q = 4:

text
        3
       / \
      5   1
     / \
    6   2
       / \
      7   4      <- p = 7, q = 4

Trace from the root down to each target. The two routes run together for a while, then split apart. The node where they split — the last one both routes pass through — is the answer. Here both 7 and 4 hang under 2, and 2's two children pull them onto different sides, so 2 is the LCA.

Find that split in one walk

No need to write out both routes. Let every node report just one thing up to its parent: "a target is somewhere below me — here it is", or null for nothing. Then each node decides by what its two children report back:

- Both children report a target → the targets sit on opposite sides of me, so the split is right here → I am the LCA.
- Only one child reports → everything found so far is on that one side → I'm not the split, I just pass that report up.
- A node that is itself p or q → reports itself right away.

Watch the reports climb:

text
        3      gets 2 from left, null from right  -> forwards 2
       / \
      5   1    1 finds nothing  -> null
     / \
    6   2      gets 7 from left, 4 from right -> BOTH -> I'm the LCA, return 2
       / \
     (7) (4)   each IS a target -> reports itself

2 is the first node to hear back from both sides, so 2 wins. Every node above it hears from only one side and just forwards the answer untouched — which is exactly why the lowest such node is the one that gets claimed.

python
def lca(node, p, q):
    if node is None or node is p or node is q:
        return node                # null, or "I am a target"
    left  = lca(node.left,  p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node                # targets split here -> I am the LCA
    return left or right           # else pass up whichever side found one

One target beneath the other? Say p = 5, q = 4 (4 lives under 5). Walking down we reach 5 first; it reports itself and stops. Since 4 is already somewhere below, 5 is the correct answer — a node counts as its own ancestor.

text
        3
       / \
    (5)   1     <- reach 5, it's a target, report it and stop
     / \
    6   2       4 is under here, but we never need to look
       / \
      7   4

One catch worth knowing: the "both sides reported" rule only works because the problem promises both p and q really exist. If one were missing, the lone target would still bubble up and some node would wrongly crown itself ancestor of a pair that isn't there. O(N) time (each node once), O(H) stack.

Interactive Strategy Visualization

Common Ancestry Audit

Bottom-Up Recursive Returns

32851
Starting search for Target A(5) and B(1). Starting DFS from Root.
Recursive Trace
Stage
Explore Root (3)
Discovery Condition

If `left` AND `right` subtrees return values, the current node is the LCA.

"Nodes report back if they found either p or q."

Strategy

Post-order traversal: A node is the LCA if it finds targets in both subtrees or if it is one of the targets and finds the other in its subtrees.

"Returns p, q, or LCA up the chain."

O(N) Two Passes · O(H) Space Compare Root Paths
→
O(N) Time · O(H) Space Single Post-order Walk