Lowest Common Ancestor

Every problem on this page asks the same question: given two nodes in a tree, where does the path down to the first one split from the path down to the second?

That question never changes. What changes is how much the problem tells you before you have to answer it - and this family is not a ladder, it is a hub with spokes. 236 is the hub. It hands you everything: the root, exactly two targets, and a promise that both are really in the tree. Every other problem here takes away exactly one of those things, and they are largely independent of each other - 1650 is not 1644 plus a change, it is 236 with a different thing missing.

The four sections below group the spokes by what the solution ends up doing: the ones that keep 236's counting walk, the ones that reduce to two chains intersecting, the one that can skip counting altogether, and the ones that have to find their own targets first. Each narrative still says what it is a variation of, which is not always the problem directly above it.

The counting rule

Narrative

The hub - everything is given. No ordering to exploit, no parent pointers, no doubt that p and q are both in the tree, and the root in hand to start from.

With every guarantee intact, have each node report how many targets live under it and take the first whose count reaches 2. Hold on to that counting rule: most of this page is that one rule with a single input changed.

236. Lowest Common Ancestor of a Binary Tree

Medium·

LCA in Binary Tree

M

236Lowest Common Ancestor of a Binary Tree

3 Approaches

DFS (Recursive)

O(n) timeO(h) aux

DFS (Recursive, Early Exit)

O(n) timeO(h) aux

DFS (Iterative, Early Exit)

O(2n) timeO(h + n) aux

FIG. LOWEST COMMON ANCESTOR RECURSIVE● INTERACTIVE

visualization loads as you reach it

def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":

def rec(node):

nonlocal lca

if not node:

return 0

left = rec(node.left) if node.left else 0

right = rec(node.right) if node.right else 0

found = left + right + int(node == p) + int(node == q)

if not lca and found == 2:

lca = node

return found

 

lca = None

rec(root)

return lca

---

Narrative

236 minus the guarantee they exist. p and q might not be in the tree at all.

The counting rule still finds a node whose subtree contains both targets when they exist, but with one target missing some node's count can still reach the value 236 trusted, for the wrong reason. The fix is not a new algorithm: it is the same post-order count carrying two extra booleans - "did I actually see p" and "did I actually see q" - and only trusting the candidate once both are true.

1644. Lowest Common Ancestor of a Binary Tree II

Medium·

1644Lowest Common Ancestor of a Binary Tree II

2 Approaches

DFS (Recursive)

O(n) timeO(h) aux

DFS (Iterative, Early Exit)

O(2n) timeO(h + n) aux

FIG. LCA BINARY TREE II RECURSIVE● INTERACTIVE

visualization loads as you reach it

def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":

def rec(node):

nonlocal lca

if not node:

return 0

left = rec(node.left) if node.left else 0

right = rec(node.right) if node.right else 0

found = left + right + int(node == p) + int(node == q)

if not lca and found == 2:

lca = node

return found

 

lca = None

rec(root)

return lca

---

Narrative

236 minus the number two. Root in hand and every target guaranteed, as in 236; what moves is the count. Instead of exactly two nodes you get a list of k.

This is the one spoke that adds nothing. 236 hard-coded the number 2 into its stopping rule, and the only edit is to stop hard-coding it: count how many of the k targets live under each node and take the first whose count reaches len(nodes). The one detail worth keeping is set(nodes) - without it, node in nodes is a linear scan at every node and the O(n) walk quietly becomes O(n*k).

1676. Lowest Common Ancestor of a Binary Tree IV

Medium·

1676Lowest Common Ancestor of a Binary Tree IV

2 Approaches

DFS (Recursive)

O(k + n) timeO(k + h) aux

DFS (Iterative, Early Exit)

O(k + 2n) timeO(k + h + n) aux

FIG. LCA BINARY TREE IV RECURSIVE● INTERACTIVE

visualization loads as you reach it

def lowestCommonAncestor(self, root: "TreeNode", nodes: "List[TreeNode]") -> "TreeNode":

def rec(node):

nonlocal lca

if not node:

return 0

left = rec(node.left) if node.left else 0

right = rec(node.right) if node.right else 0

found = left + right + int(node in nodes)

if not lca and found == len(nodes):

lca = node

return found

 

nodes = set(nodes)

lca = None

rec(root)

return lca

---

Narrative

236, but the answer is a distance, not a node. Every guarantee from the hub stays intact - root given, p and q both guaranteed to exist. What changes is the question: not "which node is the ancestor" but "how far apart are these two nodes."

The counting rule still finds the LCA exactly as in 236; the only addition is carrying depth along for the ride. Record the depth at which the recursion sits when each target is actually seen (p_depth, q_depth) and when the count first reaches 2 (lca_depth), and the distance falls out for free: (p_depth - lca_depth) + (q_depth - lca_depth) - each node's climb up to the shared ancestor, added together.

1740. Find Distance in a Binary Tree

Medium·

1740Find Distance in a Binary Tree

2 Approaches

DFS (Recursive)

O(n) timeO(h) aux

DFS (Iterative, Post-Order Stack)

O(2n) timeO(h + n) aux

FIG. FIND DISTANCE IN A BINARY TREE RECURSIVE● INTERACTIVE

visualization loads as you reach it

def findDistance(self, root: TreeNode | None, p: int, q: int) -> int:

def rec(node, depth):

nonlocal lca, p_depth, q_depth, lca_depth

if not node:

return 0

left = rec(node.left, depth + 1)

right = rec(node.right, depth + 1)

found = left + right + int(node.val == p) + int(node.val == q)

if not lca and found == 2:

lca = node

lca_depth = depth

if node.val == p:

p_depth = depth

if node.val == q:

q_depth = depth

return found

 

p_depth = q_depth = lca_depth = -1

lca = None

rec(root, 0)

return p_depth + q_depth - 2 * lca_depth

---

Intersection logic

Narrative

236 minus the root. Straight back to 236's guarantees - both nodes are present, there are exactly two - except you are never handed the root. All you get is p and q, each carrying a .parent pointer upward. (Nothing here builds on the counting section above - this is a different subtraction, not a harder one.)

Once the only way to move is "up," this stops being a tree problem. Each node's chain of .parent pointers to the root is a singly linked list, and the lowest common ancestor of two tree nodes is exactly the point where those two lists merge. This is the single best insight on the page: walk both chains with the two-pointer trick for finding where two linked lists meet (walk p to the root, then q; when a pointer runs out, redirect it to the other node; the two meet at the LCA), and the tree has nothing left to do with the algorithm at all.

Framed this way 1650 is not merely similar to a linked-list problem - it is Intersection of Two Linked Lists, solved with the identical walk, on lists that happen to be .parent chains instead of .next chains.

1650. Lowest Common Ancestor of a Binary Tree III

Medium·

1650Lowest Common Ancestor of a Binary Tree III

3 Approaches

Climb to Root, then DFS (Recursive)

O(h + n) timeO(h) aux

Ancestor Set

O(2h) timeO(h) aux

Two-Pointer Switch

O(2h) timeO(1) aux

FIG. LOWEST COMMON ANCESTOR III CLIMB THEN DFS● INTERACTIVE

visualization loads as you reach it

def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":

root = p

while root.parent:

root = root.parent

 

def lowestCommonAncestor(node):

nonlocal lca

if not node:

return 0

left = lowestCommonAncestor(node.left) if node.left else 0

right = lowestCommonAncestor(node.right) if node.right else 0

found = left + right + int(node == p) + int(node == q)

if not lca and found == 2:

lca = node

return found

 

lca = None

lowestCommonAncestor(root)

return lca

---

Narrative

1650 minus the pointers. Same shape as 1650 - two nodes, no root, climb to find where their paths merge - except nothing carries a .parent at all. You are handed a list of rows, each one a region and the regions directly inside it, and the word "tree" never appears.

Building the pointers is the whole subtraction: one pass inverting every row into parents[child] = parent and 1650 is back, unchanged. Both of its solutions transfer verbatim - the ancestor set, and the two-pointer switch that is Intersection of Two Linked Lists again, now with parents[x] as the .next. Worth sitting with, because the disguise is the point: an LCA problem does not have to mention trees, nodes, or ancestors to be one.

1257. Smallest Common Region

Medium·

1257Smallest Common Region

2 Approaches

Ancestor Set

O(m + 2h) timeO(r + h) aux

Two-Pointer Switch

O(m + 2h) timeO(r) aux

FIG. SMALLEST COMMON REGION ANCESTOR SET● INTERACTIVE

visualization loads as you reach it

class Solution:

def findSmallestRegion(self, regions: list[list[str]], region1: str, region2: str) -> str:

parents = {}

for parent, *child in regions:

for c in child:

parents[c] = parent

ancestors = set()

root = region1

while root:

ancestors.add(root)

root = parents.get(root, None)

while region2 not in ancestors:

region2 = parents.get(region2, None)

return region2

---

Binary search tree

Narrative

236 on a different tree. Same two nodes, same root, same guarantees; the tree underneath is now a binary search tree. This is the spoke that subtracts nothing and adds something instead.

It is tempting to read it as "236, but easier," since the counting solution still runs unmodified. But the ordering invariant means no node ever has to count anything: comparing p.val and q.val against node.val tells you immediately whether both targets lie to one side, in which case you descend, or whether they straddle node.val (or one of them is node.val), in which case the paths have already split and node is the answer. A different tree buys a different shape of solution, which is why 235 is a branch off this family rather than a harder version of it.

235. Lowest Common Ancestor of a Binary Search Tree

Medium·

Lowest Common Ancestor in a BST

E

235Lowest Common Ancestor of a Binary Search Tree

4 Approaches

DFS (Recursive)

O(n) timeO(h) aux

DFS (Recursive, using BST property)

O(h) timeO(h) aux

DFS (Iterative, using BST property)

O(h) timeO(1) aux

DFS (Iterative, using BST property, stackless)

O(h) timeO(1) aux

FIG. LOWEST COMMON ANCESTOR BST COUNT● INTERACTIVE

visualization loads as you reach it

class Solution:

def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":

def rec(node):

nonlocal lca

if not node:

return 0

left = rec(node.left) if node.left else 0

right = rec(node.right) if node.right else 0

found = left + right + int(node == p) + int(node == q)

if not lca and found == 2:

lca = node

return found

 

lca = None

rec(root)

return lca

---

Finding the targets first

Narrative

1676 minus the list of targets. Like 1257 two sections above, this extends a spoke rather than the hub. 1676 hands you the k nodes to cover; here you get only a rule for recognising them - they are the deepest nodes in the tree - so finding them is part of the problem.

The first solution just does it first: one sweep to learn the deepest level and how many nodes sit on it, then 1676's counting rule completely untouched, with int(depth == max_depth) doing the job node in nodes used to do. The second solution is the one worth studying: have every subtree report the deepest depth it reaches, and the answer is the highest node whose two sides report the same depth as the deepest seen anywhere. Discovery and counting collapse into a single post-order walk, and the counting disappears entirely.

1123. Lowest Common Ancestor of Deepest Leaves

Medium·

1123Lowest Common Ancestor of Deepest Leaves

2 Approaches

DFS (Recursive, Two Passes)

O(2n) timeO(h) aux

DFS (Recursive, One Pass)

O(n) timeO(h) aux

FIG. LCA DEEPEST LEAVES TWO PASS● INTERACTIVE

visualization loads as you reach it

def lcaDeepestLeaves(self, root: TreeNode | None) -> TreeNode | None:

def dfs(node, depth):

nonlocal max_depth, max_depth_nodes

if not node:

return

if max_depth < depth:

max_depth = depth

max_depth_nodes = 0

if max_depth == depth:

max_depth_nodes += 1

dfs(node.left, depth + 1)

dfs(node.right, depth + 1)

 

max_depth = max_depth_nodes = 0

dfs(root, 0)

 

def lowestCommonAncestor(node, depth):

nonlocal lca

if not node:

return 0

left = lowestCommonAncestor(node.left, depth + 1) if node.left else 0

right = lowestCommonAncestor(node.right, depth + 1) if node.right else 0

found = left + right + int(depth == max_depth)

if not lca and found == max_depth_nodes:

lca = node

return found

 

lca = None

lowestCommonAncestor(root, 0)

return lca

---

Narrative

1123 asked from the other side. Not a subtraction at all - same tree, same guarantees, same walk. 1123 asks downward, for the ancestor the deepest leaves share; 865 asks outward, for the smallest subtree that contains every deepest node.

Those land on the same node, because a subtree is named by its root, and the smallest root covering a set of nodes is their lowest common ancestor. The value in reading them back to back is learning to hear "smallest subtree containing X" as "lowest common ancestor of X" - once that translation is automatic, a whole class of subtree-flavoured questions reduces to a walk you already know.

865. Smallest Subtree with all the Deepest Nodes

Medium·

865Smallest Subtree with all the Deepest Nodes

2 Approaches

DFS (Recursive, Two Passes)

O(2n) timeO(h) aux

DFS (Recursive, One Pass)

O(n) timeO(h) aux

FIG. SUBTREE ALL DEEPEST TWO PASS● INTERACTIVE

visualization loads as you reach it

def subtreeWithAllDeepest(self, root: TreeNode | None) -> TreeNode | None:

def dfs(node, depth):

nonlocal max_depth, max_depth_nodes

if not node:

return

if max_depth < depth:

max_depth = depth

max_depth_nodes = 0

if max_depth == depth:

max_depth_nodes += 1

dfs(node.left, depth + 1)

dfs(node.right, depth + 1)

 

max_depth = max_depth_nodes = 0

dfs(root, 0)

 

def lowestCommonAncestor(node, depth):

nonlocal lca

if not node:

return 0

left = lowestCommonAncestor(node.left, depth + 1) if node.left else 0

right = lowestCommonAncestor(node.right, depth + 1) if node.right else 0

found = left + right + int(depth == max_depth)

if not lca and found == max_depth_nodes:

lca = node

return found

 

lca = None

lowestCommonAncestor(root, 0)

return lca

---

The constraint matrix, side by side:

Problem	Title	Both exist?	Root given?	How many?	What the extra structure buys
236the hub	LCA of a Binary Tree			2	Nothing - plain binary tree, counting is the only option
1644from 236	LCA of a Binary Tree II	either may be absent		2	Nothing extra; the counting answer from 236 must also prove both nodes were actually found
1676from 236	LCA of a Binary Tree IV	all k are in the tree		kgiven as a list	Nothing extra; 236's counting rule with 2 replaced by len(nodes)
1740from 236	Find Distance in a Binary Tree			2	Nothing extra; 236's counting walk with depth carried along, so the LCA's depth and each target's depth fall out for a distance instead of a node
1650from 236	LCA of a Binary Tree III		only p and q, each with a .parent pointer	2	Parent pointers turn the tree walk into a linked-list problem
1257from 1650	Smallest Common Region		no tree at all - only rows of [region, ...sub-regions]	2	Nothing until you build it - inverting the rows into a {child: parent} map recreates 1650
235branch of 236	LCA of a Binary Search Tree			2	BST ordering tells you which child to descend into without counting anything
1123from 1676	LCA of Deepest Leaves	but which nodes they are is withheld		?however many sit on the deepest level - computed, not given	Nothing extra; 1676's counting rule with the membership test replaced by depth == max_depth
865from 1123	Smallest Subtree with all the Deepest Nodes	same as 1123		same as 1123	Same as 1123, asked as a subtree instead of an ancestor