Lowest Common Ancestor of a Binary Tree: The Post-Order Count Method
The post-order count solution to Lowest Common Ancestor of a Binary Tree, explained with a worked walkthrough, JavaScript code, and full complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Given two nodes in a binary tree, find the deepest node that has both of them somewhere beneath it. That node is their lowest common ancestor — the point where the two root-to-node paths finally diverge.
The trap is that a plain binary tree gives you no ordering to exploit. You can't compare values and pick a direction the way you can in a BST. You have to actually visit nodes. The elegant fix is to let each subtree report a single number — how many of my two targets live inside me — and watch for the first subtree that reports 2.
The problem
Given the root of a binary tree and two nodes p and q that are guaranteed to exist in the tree, return their lowest common ancestor: the deepest node that has both p and q as descendants. A node is allowed to be a descendant of itself, so if p sits directly under q, then q is the answer.
3
/ \
5 1
/ \ / \
6 2 0 8
Input: root = [3,5,1,6,2,0,8], p = 6, q = 2
Output: 5 // 6 and 2 are the two children of 5Node 5 is the answer because both 6 and 2 sit in its subtree, and nothing deeper contains both. Their paths from the root — 3 → 5 → 6 and 3 → 5 → 2 — share the prefix 3 → 5 and split at 5.
The brute force baseline
The most direct idea: for any node, p and q share it as an ancestor exactly when both live in its subtree. So walk down from the root, and at each node ask "are both targets on my left?" If yes, the answer is deeper on the left; if both are on the right, go right; otherwise the split happens right here.
function contains(node, target) {
if (!node) return false;
if (node.val === target) return true;
return contains(node.left, target) || contains(node.right, target);
}
function lowestCommonAncestor(root, p, q) {
if (!root) return null;
if (contains(root.left, p.val) && contains(root.left, q.val)) {
return lowestCommonAncestor(root.left, p, q);
}
if (contains(root.right, p.val) && contains(root.right, q.val)) {
return lowestCommonAncestor(root.right, p, q);
}
return root; // both targets straddle this node — it's the split point
}This is correct but wasteful. Every contains call scans an entire subtree — O(n) — and we call it at every level as we descend. On a skewed tree that descent is n levels deep, and each level re-scans nearly the whole tree, so the work balloons to O(n²). We keep re-discovering facts about subtrees we already walked through.
The key insight
Compute the answer on the way up, not on the way down. Do one post-order pass. Each call returns a count: the number of targets (p, q, or both) found in that node's subtree. A node's count is its own match (0 or 1) plus whatever its two children reported.
The first node whose count hits 2 is the lowest common ancestor. Why the first? Because post-order resolves the deepest nodes before their parents. The deepest node that can see both targets is exactly the split point — anything below it sees at most one. We freeze the answer the moment a count reaches 2 and guard it with !lca so no shallower ancestor (which will also see count 2) overwrites it.
This count-based framing has a quiet bonus over the classic "return the node itself" trick: if one of the targets weren't actually in the tree, the count would never reach 2 and lca would correctly stay null.
The optimal solution
This is the exact algorithm the visualizer steps through — a shared lca reference, closed over by a recursive traversal that returns subtree counts.
var lowestCommonAncestor = function(root, p, q) {
let lca = null;
let traversal = (curr) => {
let count = 0;
if (!curr) return 0;
let ansOnLeft = traversal(curr.left);
let ansOnRight = traversal(curr.right);
if (curr.val === p.val || curr.val === q.val) {
++count;
}
count = count + ansOnLeft + ansOnRight;
if (count === 2 && !lca) {
lca = curr;
}
return count;
};
traversal(root);
return lca;
};The ordering inside traversal is the whole trick. Both ansOnLeft and ansOnRight are computed before this node folds them into its own count — that's what makes it post-order. The !lca guard is what pins the answer to the deepest qualifying node instead of the root.
Walkthrough
Tracing root = [3,5,1,6,2,0,8], p = 6, q = 2. Rows are in post-order — the order in which each traversal call finishes and returns its count.
| Step | Node | ansOnLeft | ansOnRight | Self match? | count | lca action |
|---|---|---|---|---|---|---|
| 1 | 6 | 0 | 0 | yes (= p) | 1 | — |
| 2 | 2 | 0 | 0 | yes (= q) | 1 | — |
| 3 | 5 | 1 | 1 | no | 2 | count === 2, !lca → lca = 5 |
| 4 | 0 | 0 | 0 | no | 0 | — |
| 5 | 8 | 0 | 0 | no | 0 | — |
| 6 | 1 | 0 | 0 | no | 0 | — |
| 7 | 3 | 2 | 0 | no | 2 | count === 2 but lca set → skip |
Step 3 is the moment of truth: 5 sums 1 from its left child (6) and 1 from its right child (2), reaches 2, and locks itself in as the LCA. Step 7 shows the guard earning its keep — the root also sees count 2 (all of 5's subtree bubbles up), but !lca blocks the overwrite, so 5 survives as the answer.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
Descend + contains scans | O(n²) | O(h) | each of up to n levels re-scans a subtree of up to n nodes |
| Post-order count | O(n) | O(h) | one visit per node; recursion stack is at most the tree height |
The optimal pass touches each of the n nodes exactly once, so time is O(n). Space is O(h) for the recursion stack, where h is the tree height. A balanced tree gives O(log n), but a skewed chain has height n — so report the space as O(h), not O(log n).
Common mistakes
- Comparing values to pick a direction. That's the BST algorithm. A plain binary tree has no ordering, so
p.val < curr.valtells you nothing about whereplives. You must visit subtrees. - Checking
count === 2without the!lcaguard. Every ancestor above the true LCA also sees count 2. Without the guard, the last one to run — usually the root — overwrites the correct answer. - Folding in children before recursing. If you check
curr.valand setcountbefore the twotraversalcalls return, you no longer have a valid subtree total. The self-match must be added, then the child counts summed, in that order. - Assuming targets might be missing. This variant guarantees both
pandqare in the tree. The count method degrades gracefully if one is absent (lca stays null), but don't rely on that unless the problem allows it. - Returning the node instead of the count.
traversalmust return the integer count so the parent frame can sum it. Return the node and the arithmetic falls apart.
Where this pattern shows up next
Post-order DFS — resolve both children, then decide at the parent — is the backbone of most binary-tree problems:
- Maximum Depth of Binary Tree — the simplest post-order fold:
1 + max(left, right). - Maximum Depth of Binary Tree - Top Down — the same measurement solved by passing depth down instead of bubbling it up.
- Balanced Binary Tree — returns a height and a balance verdict in one post-order pass.
- Diameter of Binary Tree — combines left and right heights at each node to track the longest path.
You can also step through the Lowest Common Ancestor visualizer to watch the subtree counts fill in and the LCA lock the instant a count reaches 2.
FAQ
What is the lowest common ancestor of a binary tree?
It's the deepest node that has both target nodes p and q in its subtree. Since a node counts as a descendant of itself, if one target is an ancestor of the other, that ancestor is the LCA. Equivalently, it's the node where the root-to-p and root-to-q paths last coincide before diverging.
Why can't I use value comparisons like in the BST version?
The binary search tree version works because a BST orders values — everything smaller sits left, everything larger sits right — so you can pick a direction by comparing p and q to the current node. A plain binary tree has no such ordering. A value being smaller tells you nothing about which subtree holds it, so you must actually traverse both sides.
Why does the first node with count 2 have to be the LCA?
Post-order recursion finishes a node's descendants before the node itself, so counts resolve from the leaves upward. The deepest node that can see both targets is precisely their split point; every node below it contains at most one target. The !lca guard captures that deepest node and prevents shallower ancestors — which also reach count 2 — from overwriting it.
What is the time and space complexity?
Time is O(n) because the post-order pass visits each of the n nodes exactly once and does constant work per node. Space is O(h), the recursion stack depth, where h is the tree height — O(log n) for a balanced tree but O(n) for a skewed one. The naive descend-and-scan approach is far worse at O(n²) because it re-scans subtrees at every level.
Does this handle a node being its own ancestor?
Yes. Suppose q sits inside p's subtree. When traversal reaches p, its self-match adds 1, and the subtree containing q contributes another 1, so p's count hits 2 and it locks itself in as the LCA. The definition treats a node as a descendant of itself, and the count method honors that automatically.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.