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

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)

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.

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

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 elseelse covers both “the values straddle this node” and “this node is pp or qq” — in either case you have found the split point and can stop.

	Time	Space	Needs
General tree recursion	$O(n)$	$O(h)$	Nothing
BST descent	$O(h)$	$O(1)$	The BST ordering
Path comparison	$O(n)$	$O(h)$	Nothing
Parent pointers (LC 1650)	$O(h)$	$O(1)$	`node.parentnode.parent`
Binary lifting	$O(\log n)$ /query after $O(n \log n)$ prep	$O(n \log n)$	Many queries

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]

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	`NoneNone`, the LCA, or `pp`/`qq`	236
BST	Nothing — a loop suffices	235
Parent pointers available	Nothing — two-pointer walk upward	1650 (Premium)
Deepest leaves	`(depth, lca)(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 pp and qq (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^52 <= number of nodes <= 10^5, all Node.valNode.val are unique, p != qp != q, and both exist in the tree.

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

Editorial — approach, complexity, follow-ups

One post-order traversal. Each call answers “did you find pp or qq 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)(5, 1) gives 33 — a genuine split at the root.
(5, 4)(5, 4) gives 55 — pp is an ancestor of qq, so pp is the answer. This is where “a node may be a descendant of itself” matters, and where the early return rootreturn root earns its place.
(6, 4)(6, 4) gives 55 — both in the left subtree, split at 55.
(7, 4)(7, 4) gives 22 — deep in the tree, showing the answer need not be near the root.

Follow-ups you should expect: “What if pp or qq 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)depth(p) + depth(q) - 2 * depth(lca). “Many queries on a static tree?” — binary lifting or Tarjan’s offline LCA. “LCA of kk 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 pp and qq.

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

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

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 pp and qq 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)(2, 8) gives 66 — immediate split at the root.
(2, 4)(2, 4) gives 22 — pp is an ancestor; the elseelse catches p.val == root.valp.val == root.val.
(3, 5)(3, 5) gives 44 — both descend left, then split deeper.
(0, 5)(0, 5) gives 22 — 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 pp or qq 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 pp and qq.

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 <= 10001 <= number of nodes <= 1000, 0 <= Node.val <= 10000 <= Node.val <= 1000, values are unique.

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

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, Nonereturn 0, None handles both the empty tree and, importantly, leaves: at a leaf both children return (0, None)(0, None), the depths tie, and the leaf returns (1, itself)(1, itself) — correctly making a lone deepest leaf its own answer. [1][1] returning 11 confirms this.

[0,1,3,null,2][0,1,3,null,2] returning 22 is the single-deepest-leaf case in a larger tree: node 22 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

#	Problem	Difficulty	The twist
235	Lowest Common Ancestor of a Binary Search Tree	Medium	The ordering replaces recursion — $O(h)$ , $O(1)$ space
236	Lowest Common Ancestor of a Binary Tree	Medium	Both sides reporting back means the split is here
1123	Lowest Common Ancestor of Deepest Leaves	Medium	Return a `(depth, lca)(depth, lca)` pair; a tie makes this node the answer
865	Smallest Subtree with all the Deepest Nodes	Medium	Identical to 1123, different wording
1650	Lowest Common Ancestor of a Binary Tree III	Medium · Premium	Parent pointers: two-pointer walk upward, $O(1)$ space

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 aa and bb 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

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.

Interview follow-ups

They ask	What they’re checking	The answer
“What does your recursion return?”	Whether you understand it	`NoneNone` if neither node is below; the LCA if both are; `pp` or `qq` if only one is
“Why can you return early on finding `pp`?”	Awareness of the assumption	Because both nodes are guaranteed present, so if `pp` is an ancestor of `qq` then `pp` 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
”`isis` or `====`?”	Care	Identity — values may repeat, and LeetCode hands you node objects
“Distance between two nodes?”	Composition	`depth(p) + depth(q) - 2 * depth(lca)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)(5, 4) gives 55; the case the early return handles.
The LCA is the root — nodes in opposite subtrees.
The LCA is deep — (7, 4)(7, 4) gives 22; 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 nn.

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 — NoneNone, the LCA, or one of the targets. Be able to say which.
The early return rootreturn 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)(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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Lowest Common Ancestor

What you’ll learn

The cue

The general-tree recursion

The BST shortcut

The deepest-leaves variant

The variant map

Practice — real LeetCode problems

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

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

LC 1123 — Lowest Common Ancestor of Deepest Leaves · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?