Lowest Common Ancestor Binary Tree: Three Approaches

You're given two nodes in a binary tree. Find their lowest common ancestor. The lowest common ancestor binary tree problem shows up constantly across Google, Amazon, and Meta interviews, and the common sticking point isn't the concept itself, but the recursive invariant that makes the solution clean.

What lowest common ancestor means in a binary tree

The lowest common ancestor of two nodes p and q in a binary tree is the deepest node that has both p and q as descendants. A node counts as its own descendant. A recursive postorder solution finds it in O(n) time by bubbling results up from the leaves.

That definition packs in more than you'd expect.

Deepest is what separates the lowest common ancestor from any common ancestor. The root is always a common ancestor of every pair of nodes in the tree. But the LCA is the one closest to p and q, sitting exactly where their paths from the root first diverge.

Why does this show up so often in interviews? The lowest common ancestor binary tree problem is a building block for three other problems: distance between two nodes, diameter computation through a specific pair, and range queries on tree structures. It also tests whether you can think in postorder traversal, passing information upward from children to parent, without the overhead of dynamic programming.

Outside interviews, LCA queries appear in version control systems (finding the common commit ancestor of two branches), network routing (finding the nearest shared router), and taxonomy classification. Git's merge base command, for example, is an LCA query on the commit DAG.

Finding lowest common ancestor algorithm

The most common interview solution uses a single postorder traversal. The invariant fits in one sentence. If p and q are in different subtrees of a node, that node is the LCA.

Here's the full logic: Recurse into both children first. When the left subtree contains one target and the right subtree contains the other, the current node is their lowest common ancestor. If both targets land in the same subtree, pass that result up. And if a node is one of the targets, return it immediately. The parent will figure out whether the other target is on the opposite side.

Walk through this on a concrete tree. Nodes 1 through 7, where 1 is the root. Node 2 and 3 are children of 1. Nodes 4 and 5 are children of 2. Nodes 6 and 7 are children of 3. Find the LCA of nodes 5 and 6.

The function recurses to the leaves first. At node 4, neither target matches, both children return null, so it returns null. At node 5, it matches p and returns itself. Node 2 receives null from the left (node 4) and node 5 from the right. Only one side returned a value, so node 2 passes node 5 upward.

On the right side, node 6 matches q and returns itself. Node 7 returns null. Node 3 gets node 6 from the left and null from the right, so it passes node 6 upward.

Now at the root, both sides returned non-null values. Left gave node 5, right gave node 6. The two targets split across the subtrees. Node 1 is the LCA.

The time complexity is O(n) because every node is visited at most once. Space complexity is O(h) for the recursion stack, where h is the tree's height.

Interviewers reach for this problem because it tests postorder reasoning, moving state from children to parent, without needing DP transitions or explicit memoisation. It's recursive state management at its most stripped down. If you can derive this invariant from scratch, you probably understand recursive tree algorithms well enough to handle the harder variants.

When a node might not exist (LCA II)

The standard LCA problem guarantees that both p and q exist in the tree. LCA II removes that guarantee. If either node isn't present, return null.

One missing node changes everything.

Why does this break the original algorithm? The standard version returns early when it finds p or q, so it never actually checks whether the other node exists anywhere in the tree. With LCA II, you can't short circuit like that. You need to traverse every node to confirm both targets are actually present.

Instead of returning the node itself, each recursive call returns two booleans tracking whether p and q have been found. The LCA is set only when both are confirmed found for the first time. This catches the false positive that the standard algorithm would produce when p exists but q doesn't.

Finding distance between two nodes using LCA

Once you have the LCA, computing the distance between two nodes is a clean decomposition. The distance between p and q equals the depth of p relative to the LCA plus the depth of q relative to the LCA.

The formula works because the path between any two nodes in a tree must pass through their LCA. There's no shorter route. You find the LCA in O(n), then compute two depths with partial traversals from the LCA downward. The total stays O(n).

Remember this decomposition. It converts a path between nodes problem into two simpler root to node problems. The same reduction works for path sums between arbitrary nodes or finding the maximum edge weight on a tree path. Any time you need to reason about a path between two arbitrary nodes, ask yourself whether you can route through the LCA and decompose the problem into two downward traversals.

Binary lifting for repeated queries

The postorder solution is optimal for a single LCA query. But what if you need to answer thousands of LCA queries on the same tree? Running O(n) per query adds up quickly.

Binary lifting preprocesses the tree in O(n log n) time and answers each LCA query after that in O(log n).

For every node, precompute its ancestor at distance 1, 2, 4, 8, 16, and so on (powers of 2). Store these in a table up[node][k], where the entry is the ancestor of that node at distance 2^k.

To find the LCA of two nodes, first bring them to the same depth by jumping the deeper node upward using the precomputed table. Then jump both nodes upward in decreasing powers of 2, skipping any jump that lands them on the same node. When no more jumps are possible, the direct parent of either node is the LCA.

Binary lifting comes up in competitive programming and in problems that combine LCA with other tree queries (path sums, edge weights, tree diameter through specific pairs). Most coding interviews stick to the single query O(n) version. But knowing the sparse table method shows you can think about scaling, and that's the kind of followup senior level interviewers like to explore.

The skills LCA ties together

The lowest common ancestor pattern ties together several binary tree skills: postorder state propagation, recursive invariant construction, and tree path decomposition. If postorder traversal still feels shaky, start there before attempting LCA variants.

Codeintuition's understanding lesson for the lowest common ancestor pattern walks through the invariant frame by frame before any code. The identification lesson that follows trains you to spot when a problem reduces to LCA, which is the step that usually gets skipped. The full Binary Tree course covers LCA as one of six traversal-based patterns across 47 lessons and 62 problems.

For the complete picture of how tree patterns connect to recursion, traversal, and interview strategy, the full guide to binary trees and recursion covers every pattern in context.

The learning path starts with two permanently free courses on Arrays and Singly Linked Lists that build the recursive thinking foundations tree problems depend on. No trial period, no paywall countdown.

Six months ago, you stared at an LCA problem and tried to work out the recursion from scratch. Where do you start the traversal? What do you return at each level? Now you see an unfamiliar tree problem, recognise the postorder invariant, and write the three line core from understanding. The distance variant and LCA II follow directly. That shift doesn't come from solving more problems. It comes from learning the invariant first.