Lowest Common Ancestor

The lowest common ancestor of two nodes is the deepest node that has both of them as descendants. The obvious approach — find the path to each node, then compare the paths — works and costs $O(n)$ time plus $O(h)$ space for the two paths.

The elegant approach is six lines, and it turns on one observation:

If the left subtree reports back “I found one of them” and the right subtree reports back “I found one of them”, then the two nodes are split across this node — so this node is the LCA.

If only one side reports back, the LCA is somewhere in that side, so pass the report upward unchanged. That is the whole algorithm.

What you’ll learn

• The general-tree recursion, and precisely what its return value means.
• Why the BST version collapses to a loop with $O(1)$ space.
• The deepest-leaves variant, where the recursion returns a pair.
• What changes when nodes are not guaranteed to exist, or parent pointers are available.
• Three real LeetCode problems solved in the browser: 236, 235, 1123.

The cue

You are looking at an LCA problem when…

• “Lowest / deepest common ancestor” of two or more nodes — 236, 235, 1676.
• “The smallest subtree containing all of X” — 865, 1123. Same thing phrased differently.
• Distance between two nodes in a tree — find the LCA, then depth(p) + depth(q) - 2 * depth(lca).
• You need the meeting point of two root-to-node paths.
• Repeated ancestor queries on a static tree — that is binary lifting, an $O(\log n)$-per-query preprocessing technique beyond this page’s scope.

Visual intuition

The split case: p and q are on opposite sides, so the node where both recursive calls return non-None is the answer.

treeLC 236: the LCA is the node whose two subtrees each return a hitgeneral tree · O(n) time, O(h) space

1def lca(node, p, q):2    if node is None or node.val in (p, q):3        return node4    left  = lca(node.left,  p, q)5    right = lca(node.right, p, q)6    if left and right:7        return node          # p and q split here → this is the LCA8    return left or right     # both targets on one side

returnsNone

bubbleNeither subtree of 6 contains a target, so 6 returns None.

Play‹›1/10⟲

Node 2 is the first node where the left call and the right call both come back non-None, so it is the LCA. Above it, node 5 receives a hit from one side only and passes it up unchanged -- which is what 'return left or right' means: 'I found something below me, but not the meeting point'.

And the ancestor case, which is where the algorithm’s guarantee earns its keep:

treeWhen p is an ancestor of q: the walk returns 5 without ever visiting 4the guarantee is load-bearing

1def lca(node, p, q):2    if node is None or node.val in (p, q):3        return node4    left  = lca(node.left,  p, q)5    right = lca(node.right, p, q)6    if left and right:7        return node          # p and q split here → this is the LCA8    return left or right     # both targets on one side

node5

found5 is one of the two targets. Return it upward — the recursion does not need to search below a target, because any node below it would have this node as its ancestor anyway.

Play‹›1/6⟲

Node 5 is p, so it returns itself on sight and its whole subtree -- including q at node 4 -- is never examined. That is correct only because the problem guarantees both nodes exist in the tree. Remove that guarantee and this answer is wrong for a q that is not present.

The general-tree recursion

lca_general.py

def lowest_common_ancestor(root, p, q):
    if not root or root is p or root is q:
        return root                 # found one of them, or ran out of tree
 
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
 
    if left and right:
        return root                 # p and q are on opposite sides -> this is the LCA
    return left or right            # both are in one side (or neither is here)

$O(n)$ time, $O(h)$ space for the recursion.

What the return value actually means

This is the part worth being able to state precisely, because the function’s return value carries two different meanings depending on the situation:

• None — neither p nor q is in this subtree.
• The LCA — if both are in this subtree.
• p or q itself — if only one of them is in this subtree.

The third case is why if root is p or root is q: return root can stop immediately without looking deeper. Given the problem’s guarantee that both nodes exist in the tree, if p is an ancestor of q then p is the LCA — so returning p on sight is correct, and there is no need to confirm q is below it.

That guarantee is load-bearing. Remove it and the algorithm breaks — see the follow-ups.

Compare identity, not values

Use root is p, not root.val == p.val. Trees can contain duplicate values, and LeetCode passes the actual node objects. Comparing values finds the wrong node whenever a duplicate appears above the real one.

LC 236 happens to guarantee unique values, so == passes there — but the habit is wrong and it fails the moment duplicates are allowed.

The BST shortcut

In a BST the ordering tells you which way to go, so no recursion is needed at all:

lca_bst.py

def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left          # both smaller: LCA is in the left subtree
        elif p.val > root.val and q.val > root.val:
            root = root.right         # both larger: LCA is in the right subtree
        else:
            return root               # they split here, or one IS this node
    return None

$O(h)$ time, $O(1)$ space. The else covers both “the values straddle this node” and “this node is p or q” — in either case you have found the split point and can stop.

Complexity

Approach	Time	Space	Needs
General tree recursion	$O(n)$	$O(h)$	Nothing
BST descent	$O(h)$	$O(1)$	The BST ordering
Path comparison (root-to-node lists)	$O(n)$	$O(h)$	Nothing
Parent pointers (LC 1650)	$O(h)$	$O(1)$	node.parent
Binary lifting	$O(\log n)$/query after $O(n \log n)$ prep	$O(n \log n)$	Many queries, static tree
Euler tour + sparse table	$O(1)$/query after $O(n \log n)$ prep	$O(n \log n)$	Many queries, and the constant matters

The general recursion is $O(n)$ and not $O(h)$ because it has no ordering to steer by — it must be prepared to search the whole tree. It often stops early in practice (the ancestor case above visits 5 of 9 nodes), but the bound is every node, and a tree where p and q sit in the last subtree explored achieves it.

Choose on the query count: one query, use the recursion; a BST, use the descent ($O(1)$ space, and it fits on a whiteboard); many queries on a static tree, preprocess with binary lifting.

Dry run

Split case — lca(root, p=7, q=4) on [3,5,1,6,2,0,8,null,null,7,4]. Post-order, so the deepest answers resolve first.

node	left call	right call	returns	meaning
6	None	None	None	neither node is here
7	—	—	7	root is p, return on sight
4	—	—	4	root is q, return on sight
2	7	4	2	both sides hit → this is the LCA
5	None (from 6)	2	2	one side hit → pass it up unchanged
0, 8	—	—	None	—
1	None	None	None	the whole right subtree is empty of both
3	2	None	2	one side hit → pass up; the answer surfaces

LCA = 2. Note that node 2’s return root and node 5’s return left or right are doing different jobs with the same value: node 2 decided, node 5 merely relayed.

Ancestor case — lca(root, p=5, q=4). Visits, in order: 3, 5, 1, 0, 8. Then it stops.

• Node 4 is never visited. Node 5 is p, so it returns itself immediately and its entire subtree — including q — goes unexamined.
• That is correct only because both nodes are guaranteed present. If q were not in the tree, this returns 5 for a question that has no answer. The fix, if the guarantee is dropped, is to search the whole tree and count how many of p and q were actually found before trusting the result.
• The right subtree is still fully walked (1, 0, 8) even though the answer was already determined on the left. The recursion cannot know that, which is another way of seeing why the bound is $O(n)$.

Deepest-leaves variant on the same tree (LC 1123): depths tie at node 2 (leaves 7 and 4 are both at depth 3), so dfs returns (depth, node 2) and the tie propagates upward as the answer — 2 again, for an entirely different reason.

The deepest-leaves variant

LC 1123 and LC 865 ask for the LCA of all the deepest leaves, which you do not know in advance. The trick is to have the recursion return two things at once: the subtree’s depth, and the LCA of the deepest leaves within it.

lca_deepest_leaves.py

def lca_deepest_leaves(root):
    def dfs(node):
        """Return (depth of this subtree, LCA of its deepest leaves)."""
        if not node:
            return 0, None
        left_depth, left_lca = dfs(node.left)
        right_depth, right_lca = dfs(node.right)
 
        if left_depth == right_depth:
            return left_depth + 1, node      # TIE -> this node is the meeting point
        if left_depth > right_depth:
            return left_depth + 1, left_lca  # deepest leaves are all on the left
        return right_depth + 1, right_lca
 
    return dfs(root)[1]

The tie is the insight: if both sides are equally deep, the deepest leaves live on both sides, so their common ancestor must be this node. If one side is strictly deeper, all the deepest leaves are in it, and its answer propagates upward unchanged.

This is a cousin of the split-brain idea from Tree DFS: return a summary the parent can use, while separately determining an answer that is complete at this node.

The variant map

Variant	What the recursion returns	Canonical problem
General binary tree	None, the LCA, or p/q	236
BST	Nothing — a loop suffices	235
Parent pointers available	Nothing — two-pointer walk upward	1650 (Premium)
Deepest leaves	(depth, lca) pair	1123 · 865
Nodes may not exist	Add explicit found-flags	1644
LCA of many nodes	Fold the pairwise LCA across the set	1676
Distance between two nodes	LCA, then depth arithmetic	1740

Practice — real LeetCode problems

LC 236 — Lowest Common Ancestor of a Binary Tree · Medium

Problem. Given the root of a binary tree and two nodes p and q (both guaranteed to exist in the tree), return their lowest common ancestor. A node may be a descendant of itself.

Constraints. 2 <= number of nodes <= 10^5, all Node.val are unique, p != q, and both exist in the tree.

Examples. For [3,5,1,6,2,0,8,null,null,7,4]: LCA of 5 and 1 is 3 · LCA of 5 and 4 is 5 (a node can be its own descendant)

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

One post-order traversal. Each call answers “did you find p or q below you, and if both, where did they meet?”.

Time $O(n)$ — every node visited at most once. Space $O(h)$.

The four test cases cover the distinct shapes:

• (5, 1) gives 3 — a genuine split at the root.
• (5, 4) gives 5 — p is an ancestor of q, so p is the answer. This is where “a node may be a descendant of itself” matters, and where the early return root earns its place.
• (6, 4) gives 5 — both in the left subtree, split at 5.
• (7, 4) gives 2 — deep in the tree, showing the answer need not be near the root.

The early return relies on both nodes existing

if root is p: return root stops without checking that q is actually below. That is correct only because the problem guarantees both nodes are in the tree.

If q might be absent, this returns p when the true answer should be “no LCA exists”. LC 1644 is precisely that variant, and the fix is to do a full traversal counting how many of the two you found, returning the candidate only when the count reaches 2. If an interviewer removes the existence guarantee, this is what they are testing.

Follow-ups you should expect: “What if p or q might not exist (LC 1644)?” — as above. “With parent pointers (LC 1650)?” — walk up from each node; the elegant trick is two pointers that switch to the other node’s start when they hit the root, meeting at the LCA in $O(h)$ and $O(1)$ space — the same idea as the linked-list-intersection problem. “Distance between two nodes?” — depth(p) + depth(q) - 2 * depth(lca). “Many queries on a static tree?” — binary lifting or Tarjan’s offline LCA. “LCA of k nodes (LC 1676)?” — fold the pairwise LCA across them, since LCA is associative.

LC 235 — Lowest Common Ancestor of a Binary Search Tree · Medium

Problem. Same question, but the tree is a BST. Return the LCA of p and q.

Constraints. 2 <= number of nodes <= 10^5, unique values, p != q, both exist in the tree.

Examples. For [6,2,8,0,4,7,9,null,null,3,5]: LCA of 2 and 8 is 6 · LCA of 2 and 4 is 2

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The LCA is the first node where the two values stop agreeing about direction. While both are smaller, both live left; while both are larger, both live right. The moment they disagree — or one equals the current node — you are standing on the split point.

Time $O(h)$. Space $O(1)$.

Compare this with LC 236: the general version must explore both subtrees because it has no way to know where p and q are. The BST version never explores a subtree it does not need, which is what turns $O(n)$/$O(h)$ into $O(h)$/$O(1)$.

The test cases cover each branch:

• (2, 8) gives 6 — immediate split at the root.
• (2, 4) gives 2 — p is an ancestor; the else catches p.val == root.val.
• (3, 5) gives 4 — both descend left, then split deeper.
• (0, 5) gives 2 — split at an internal node.

Follow-ups you should expect: “Recursive version?” — same three conditions, recursing instead of looping; $O(h)$ space for no gain. “What if the BST is unbalanced?” — $O(h)$ becomes $O(n)$. “What if p or q might not be present?” — the descent still terminates but you must verify both exist, costing an extra $O(h)$ search each. “Why does the BST case not need to know which node is smaller?” — because both comparisons are tested independently, so the code is symmetric in p and q.

LC 1123 — Lowest Common Ancestor of Deepest Leaves · Medium

Problem. Return the lowest common ancestor of the deepest leaves of the tree. If there is a single deepest leaf, the answer is that leaf.

Constraints. 1 <= number of nodes <= 1000, 0 <= Node.val <= 1000, values are unique.

Examples. [3,5,1,6,2,0,8,null,null,7,4] gives 2 (deepest leaves are 7 and 4) · [1] gives 1 · [0,1,3,null,2] gives 2

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

You cannot identify the deepest leaves before traversing, so compute depth and answer together, bottom-up.

At each node:

• Equal child depths — the deepest leaves are distributed across both sides, so their lowest common ancestor is this node.
• One side strictly deeper — every deepest leaf is in that side, so its answer is still the answer here.

Time $O(n)$, one pass. Space $O(h)$.

The base case return 0, None handles both the empty tree and, importantly, leaves: at a leaf both children return (0, None), the depths tie, and the leaf returns (1, itself) — correctly making a lone deepest leaf its own answer. [1] returning 1 confirms this.

[0,1,3,null,2] returning 2 is the single-deepest-leaf case in a larger tree: node 2 is the only node at the maximum depth, so it is its own LCA.

The naive alternative is two passes — find the max depth, collect the leaves at that depth, then fold LC 236’s pairwise LCA over them. That is $O(n)$ per LCA call and $O(n^2)$ overall in the worst case. The paired return does it in one pass.

This is also LC 865 (Smallest Subtree with all the Deepest Nodes) word for word — the same problem under a different title, so solving one gives you both.

Follow-ups you should expect: “Return the depth as well?” — it is already in the pair. “What if you wanted the LCA of all leaves at a given depth?” — same recursion with the target depth passed down. “Iteratively?” — BFS to find the deepest level, then fold pairwise LCAs; more code and worse complexity.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1650 is the linked-list intersection problem in disguise

With parent pointers, the two root-to-node paths are two linked lists that merge at the LCA. So the classic two-pointer trick applies: walk a and b upward one step at a time, and whenever a pointer reaches the root, restart it at the other node’s start. Both pointers then traverse the same total number of steps and meet exactly at the LCA.

python

a, b = p, q
while a is not b:
    a = a.parent if a.parent else q
    b = b.parent if b.parent else p
return a

$O(h)$ time, $O(1)$ space, no set of visited ancestors needed. Recognising it as LC 160 (Intersection of Two Linked Lists) rather than a tree problem is the whole insight.

6 problems

0 easy6 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○236Lowest Common Ancestor of a Binary TreemediumBoth sides reporting back means the split is hereLeetCode Top Interview 150metaamazonmicrosoftapple
• ○235Lowest Common Ancestor of a Binary Search TreemediumThe ordering replaces recursion -- $O(h)$, $O(1)$ spaceNeetCode 150Blind 75
• ○865Smallest Subtree with all the Deepest NodesmediumIdentical to 1123, different wording
• ○1123Lowest Common Ancestor of Deepest LeavesmediumReturn a `(depth, lca)` pair; a tie makes this node the answer
• ○1650Lowest Common Ancestor of a Binary Tree IIIpremiummediumParent pointers: two-pointer walk upward, $O(1)$ space
• ○2096Step-By-Step Directions From a Binary Tree Node to Anothermedium

Interview follow-ups

They ask	What they’re checking	The answer
“What does your recursion return?”	Whether you understand it	None if neither node is below; the LCA if both are; p or q if only one is
“Why can you return early on finding p?”	Awareness of the assumption	Because both nodes are guaranteed present, so if p is an ancestor of q then p is the LCA
“What if a node might be missing?”	The boundary	The early return breaks; do a full traversal counting finds and only accept the candidate at count 2 (LC 1644)
“Why is the BST version better?”	Using the structure	The ordering says which subtree to enter, so you never explore both — $O(h)$ and $O(1)$ space
“is or ==?”	Care	Identity — values may repeat, and LeetCode hands you node objects
“Distance between two nodes?”	Composition	depth(p) + depth(q) - 2 * depth(lca)
“Thousands of queries on one tree?”	Breadth	Binary lifting ($O(\log n)$ per query after $O(n \log n)$ prep), or Tarjan’s offline LCA with union-find

Edge-case checklist

• One node is an ancestor of the other — (5, 4) gives 5; the case the early return handles.
• The LCA is the root — nodes in opposite subtrees.
• The LCA is deep — (7, 4) gives 2; the answer need not be near the root.
• Two-node tree — the minimum size LC 236 allows.
• Single node (LC 1123) — it is its own answer.
• Single deepest leaf — returns that leaf, not its parent.
• Duplicate values — compare by identity; LC 236 forbids them but the habit matters.
• Node not in the tree — breaks the standard solution; LC 1644 is the variant that handles it.
• Degenerate chain — $O(h) = O(n)$; also a recursion-depth risk at large n.

Self-check

pch.quizTag Lowest common ancestor — self-check

1. What does the recursion's return value mean?

   A Always the LCA of the whole tree B Three things depending on the subtree: None if neither node is in it, p or q itself if only one is, and the LCA if both are C The depth of the deeper node D True or False, encoded as a node
   pch.quizShowAnswer

   B — Three things depending on the subtree: None if neither node is in it, p or q itself if only one is, and the LCA if both are — Being able to state all three cases is what separates understanding this algorithm from having memorised six lines. `if left and right: return root` is case three; `return left or right` relays cases one and two.

2. `if root is p or root is q: return root` stops without checking whether the other node is below. Why is that correct?

   A It is not correct B Because the problem guarantees both nodes exist in the tree — so if p is an ancestor of q, p is the LCA and no confirmation is needed C Because p and q are always leaves D Because the tree is a BST
   pch.quizShowAnswer

   B — Because the problem guarantees both nodes exist in the tree — so if p is an ancestor of q, p is the LCA and no confirmation is needed — In the ancestor dry run, node 4 is never visited. Drop the existence guarantee (LC 1644) and this returns an answer for a question with none — then you must search the whole tree and count the hits.

3. Why `root is p` rather than `root.val == p.val`?

   A It is faster B Because trees may contain duplicate values and LeetCode passes actual node objects — comparing values finds the wrong node whenever a duplicate sits above the real one C Because vals may be None D They are equivalent in Python
   pch.quizShowAnswer

   B — Because trees may contain duplicate values and LeetCode passes actual node objects — comparing values finds the wrong node whenever a duplicate sits above the real one — LC 236 guarantees unique values so `==` passes there, which is exactly why the habit goes unpunished until a variant allows duplicates.

4. In a BST, why is the iterative descent better than the general recursion?

   A It is not; they are the same B The ordering tells you which way to go, so it is O(h) time and O(1) space with no recursion — and the `else` branch covers both 'the values straddle this node' and 'this node is p or q' C Because it handles duplicates D Because it works on any tree
   pch.quizShowAnswer

   B — The ordering tells you which way to go, so it is O(h) time and O(1) space with no recursion — and the `else` branch covers both 'the values straddle this node' and 'this node is p or q' — The general recursion must be prepared to search everything, hence O(n). With an ordering to steer by there is nothing to search — you walk one path down.

5. LC 1123 asks for the LCA of all deepest leaves, which you do not know in advance. What is the trick?

   A Find the deepest leaves first, then run LCA pairwise B Return two things per node — subtree depth and the LCA of its deepest leaves — and treat a depth TIE as 'this node is the meeting point' C Use a BFS to find the last level D Binary lifting
   pch.quizShowAnswer

   B — Return two things per node — subtree depth and the LCA of its deepest leaves — and treat a depth TIE as 'this node is the meeting point' — A tie means the deepest leaves live on both sides, so their common ancestor is this node; a strictly deeper side propagates its own answer upward. It is the split-brain idea from the Tree DFS page: return a summary the parent can use, decide separately what is complete here.

6. You must answer 10^5 LCA queries on one fixed tree. What changes?

   A Nothing — O(n) per query is fine B Preprocess: binary lifting gives O(log n) per query after O(n log n) setup; break-even is around log n queries C Cache each answer in a dict D Convert the tree to a BST
   pch.quizShowAnswer

   B — Preprocess: binary lifting gives O(log n) per query after O(n log n) setup; break-even is around log n queries — O(nq) is 10^10 on a 10^5-node tree. Caching helps only if queries repeat. The jump table is the standard answer, and Euler tour + sparse table gets O(1) per query if the constant matters.

Recall card

• Cue — “lowest common ancestor”, or any “where do these two paths meet” question in a tree.
• General tree — return root if it is p or q; recurse both sides; both sides non-None → this node is the LCA; otherwise return left or right.
• Return value means three things — None (neither here), p/q (only one here), the LCA (both here).
• BST — descend: both smaller → left, both larger → right, else this is the split point. $O(h)$ time, $O(1)$ space.
• Compare identity (is), never values — duplicates break value comparison.
• The existence guarantee is load-bearing — returning p on sight is only valid because q is known to be in the tree (contrast LC 1644).
• Deepest leaves (LC 1123) — return (depth, lca); a depth tie means this node is the answer.
• Many queries — binary lifting, $O(\log n)$ per query after $O(n \log n)$ preprocessing.

Recap

• If both subtrees report a find, this node is the LCA. If only one does, pass its report upward. Six lines, $O(n)$ time, $O(h)$ space.
• The return value means three different things — None, the LCA, or one of the targets. Be able to say which.
• The early return root depends on both nodes existing. Remove that guarantee and you need explicit found-counting.
• A BST replaces the recursion with a loop: descend while both values agree on direction, stop when they split. $O(h)$ time, $O(1)$ space.
• Compare by identity, not by value.
• For deepest leaves, return a (depth, lca) pair and let a depth tie identify the meeting point — one pass instead of $O(n^2)$.
• With parent pointers it becomes the linked-list intersection two-pointer trick.

Next: Tree Construction from Traversals — rebuilding a tree from its preorder and inorder sequences, and why one traversal is never enough.