LCA and Parent Pointers

The lowest common ancestor (LCA) of two nodes is the deepest node that has both of them in its subtree. It is the meeting point you need whenever a problem connects two nodes: the distance between them, the path from one to the other. The same family of problems often needs to move up the tree, and the fix for that is to add parent pointers.

The idea#

The LCA is a postorder decision. Each call asks its left and right subtrees "did you find P or Q?" and bubbles the answer up. The decision at each node is always the same:

Situation at this node	Return
This node is P or Q	this node
Left and right both returned something	this node: it is the LCA
Only one side returned something	that value (a target, or an LCA already found below)
Neither side returned anything	`None`

Why it works: P and Q sit in different subtrees only at their LCA, so that is the one node where both sides report a hit. Above it, only one side reports, and the found LCA travels up unchanged. If P is an ancestor of Q, the walk returns P as soon as it reaches it. That is correct, because a node counts as its own ancestor.

A tree where P and Q are leaves under different children of node A. Each child returns the target it found; node A sees both sides return something and returns itself, and the root passes A up unchanged

LCA answers how two nodes meet. Other questions start at one node and spread outward, up as well as down. Trees only point downward, so if you need to climb up, add a parent pointer. One DFS records parent[child] = node for every node. The tree then behaves like an undirected graph, and BFS from any node finds distances in every direction.

How to spot it#

These cues point to LCA or parent pointers.

Two given nodes and a question about how they connect: common ancestor, distance, directions.
"Distance k from a target node", "time to spread from a start node": the walk must go up as well as down.
Nodes that already have a parent field.
A BST and two values: the LCA is where the values split.

Template#

This is the LCA decision table as pseudocode. Nodes follow LeetCode's TreeNode(val, left, right).

lca(node, p, q):
    if node is None or node is p or node is q:
        return node                  # empty, or this node is a target
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right both found something:
        return node                  # targets split here
    return whichever side found something, or None

Parent pointers, then BFS#

The LCA template only moves down. When the walk must go up, record parents first. Then search outward from a start node as in any graph.

parent = {root: None}
walk the tree once; for each child: parent[child] = node
seen = {start}; frontier = [start]
while the frontier is not empty (or until enough rings):
    next ring = unseen nodes among left, right and parent
                of every node in the frontier
    mark them seen; frontier = next ring

A ring is the set of nodes exactly one step further from the start than the ring before it.

Pitfalls#

These mistakes give None or loop forever.

Returning from the helper instead of the outer function. Some variants (such as Deepest Leaves) use a helper that returns a tuple. The outer function must unpack it. A return placed after another return inside the helper never runs.
Comparing values instead of nodes. node.val == p.val works only when values are unique. Prefer node is p.
Climbing without a visited set. Once parent links exist, the structure has cycles (child to parent and back). Mark visited nodes, as with any graph.
Forgetting that a node is its own ancestor. If P is above Q, the answer is P.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Lowest Common Ancestor of a Binary Tree

This is the template. Return yourself if you are a target; otherwise pass up whichever side found something.

Hint: Lowest Common Ancestor of a Binary Search Tree

The ordering removes the need to backtrack. If both values are smaller than the node, go left; if both are larger, go right. Otherwise they split here (or one of them is this node), so this node is the LCA. A loop does it in $O(h)$ .

Hint: Lowest Common Ancestor of Deepest Leaves

Return a pair (lca_of_deepest, depth) from each subtree. If both sides report the same depth, this node is the answer; otherwise pass up the deeper side's pair. The outer function returns helper(root, 0)[0]. Keep that line in the outer function, not after a return inside the helper.

Hint: Step-By-Step Directions From a Binary Tree Node to Another

Find the LCA first. Record the path from the LCA down to each node with a backtracking search that appends "L" or "R" and pops on a dead end. The answer is "U" once per step of the path to the start, then the path to the destination.

Hint: Lowest Common Ancestor of a Binary Tree III

Each node has a parent field. Walk up from P and put every ancestor in a set, then walk up from Q until you hit one. For $O(1)$ space, use the linked-list intersection trick: each pointer jumps to the other start when it reaches the top. Compare nodes by identity.

Hint: All Nodes Distance K in Binary Tree

Record every node's parent in one pass. Then run BFS from the target over left, right and parent, with a visited set. Stop after k rings; the frontier holds the answer.

Hint: Amount of Time for Binary Tree to Be Infected

The infection spreads up as well as down, so record parents first. Run BFS from the start node, one ring per minute. The answer is the number of rings after the first, until no new node is reached.

Key takeaways#

LCA is a postorder status report: both sides found something, so this node is the meeting point.
Return yourself if you are a target; otherwise pass up whichever side found something.
In a BST, the LCA is where the two values split.
To move up the tree, record parents; the tree becomes an undirected graph.
With parent links, use a visited set like any graph search.

Core idea#

The lowest common ancestor (LCA) of two nodes is the deepest node with both in its subtree. Find it with a postorder status report. To move up the tree, add parent pointers.

The LCA decision#

At this node	Return
Node is P or Q	this node
Both sides returned something	this node: the LCA
One side returned something	that value
Neither side	`None`

Key points#

P and Q sit in different subtrees only at their LCA. Above it, the found LCA travels up unchanged.
A node is its own ancestor. If P is above Q, the answer is P.
BST: both values smaller, go left. Both larger, go right. Otherwise this node is the LCA. Cost $O(h)$ .
Parent pointers: one DFS records parent[child] = node. The tree becomes an undirected graph. BFS from any node finds distances in all directions.
Given parent fields: put P's ancestors in a set, then climb from Q. Or use the list-intersection trick for $O(1)$ space.
Deepest leaves: return (lca, depth). Equal depths on both sides make this node the answer.
Directions: find the LCA, then "U" per step to the start plus the path to the destination.

Template#

lca(node, p, q):
    if node is None or node is p or node is q:
        return node                  # empty, or a target
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right both found something:
        return node                  # targets split here
    return whichever side found something, or None

Pitfalls#

Comparing values instead of nodes. Use node is p.
Climbing without a visited set. Parent links create cycles.
Deepest leaves: keep return helper(root, 0)[0] in the outer function. Placed after another return inside the helper, it never runs.

Say it in an interview#

"If both subtrees report a target, this node is the LCA."
"To walk up, record parents and treat the tree as an undirected graph."