Lowest Common Ancestor of a Binary Tree

Given a binary tree and two distinct nodes p and q, return their lowest common ancestor (the deepest node that has both in its subtree).

Why this is worth learning

The return value summarizes whether the subtree contains a target or already contains their common ancestor. Target identity is a pointer relation, not a value comparison.

Before coding: one-minute experiment

If p is an ancestor of q, should the answer be p or p’s parent?

Function signature

func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode

Inputs / outputs

• root: root of the tree.
• p, q: pointers to two distinct nodes in the tree.
• Return: pointer to the LCA node.

Example

Tree: [3,5,1,6,2,0,8]
p = 5, q = 1
Output: 3

Constraints

• 1 <= number of nodes <= 100_000

Core idea (near-solution)

A direct solution stores each target's root-to-node path and finds their last shared pointer. Recursion can compress that evidence: a child returns nil for no target evidence, a target pointer when it finds one, or an already-established common ancestor. If both child results are non-nil, their evidence splits here and this node is the lowest point joining it. If only one is non-nil, propagate it. Returning immediately at p or q handles the ancestor case because both target pointers are promised present; a missing-target API would need additional presence evidence.

Invariant: DFS returns nil if the subtree has no target, otherwise returns the target or the LCA found below.

Algorithm (step-by-step)

1. If root is nil or equals p or q, return root.
2. Recurse into left and right subtrees.
3. If both results are non-nil, root is the LCA.
4. Otherwise return the non-nil result (or nil if neither).

Correctness sketch

If the current root is nil, it contains neither target. If it is p or q, return that node: because both targets are guaranteed to exist in the original tree, it is a valid ancestor candidate even when the other lies below it. Otherwise recurse into both children. Non-nil results from both sides mean the targets split across the two child subtrees, making the current node their lowest common ancestor. A result from only one side contains all target evidence found here, so propagate it unchanged. No deeper node can be common when the targets split, and propagation preserves an already deeper candidate, proving lowestness.

Trace (hand walkthrough)

Example input:
Tree: [3,5,1,6,2,0,8]
p = 5, q = 1
Output: 3

Walk:
- DFS at node 5 returns 5 (matches p).
- DFS at node 1 returns 1 (matches q).
- At node 3, left=5 and right=1 are both non-nil => LCA = 3.

Pitfalls to avoid

• Treating values as identifiers when duplicates could exist; use node pointers.
• Missing the base case where root is p or q.

Debugging lens

Use equal-valued distinct nodes and targets where one is an ancestor of the other. Both p and q are distinct pointers present in the tree; the reference is not a general missing-target validator.

Complexity

• Time: O(n).
• Extra space: O(h) recursion depth.

Implementation notes (Go)

• The tree nodes in tests are pointer-identity unique; compare pointers directly.

Reconstruction checkpoint

Suppose p is present but q is an unrelated allocated node outside the tree. What could the current recursion return? What extra information would support an API that must report missing targets?

Return to Binary Tree General · Module quiz