Skip to main content

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.

351620874LCAfirst place both paths meetpqclimb up from pclimb up from q
Otto grabs both targets and follows each one's path upward: the lowest common ancestor is the first node the two climbs share.
maybe absentk nodesdistanceno rootno pointersBSTunlistedsubtree236LCA1644LCA II1676LCA IV1740Distance1650LCA III1257Common Region235BST LCA1123Deepest Leaves865Deepest Subtree

The counting rule​

Otto, your interviewer

236. Lowest Common Ancestor of a Binary Tree​

236

Lowest Common Ancestor of a Binary Tree

LeetCode
Medium

DFS (Recursive)

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
top ↑
Otto, your interviewer

1644. Lowest Common Ancestor of a Binary Tree II​

1644

Lowest Common Ancestor of a Binary Tree II

LeetCode
Medium

DFS (Recursive)

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
top ↑
Otto, your interviewer

1676. Lowest Common Ancestor of a Binary Tree IV​

1676

Lowest Common Ancestor of a Binary Tree IV

LeetCode
Medium

DFS (Recursive)

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
top ↑
Otto, your interviewer

1740. Find Distance in a Binary Tree​

1740

Find Distance in a Binary Tree

LeetCode
Medium

DFS (Recursive)

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
top ↑

Intersection logic​

Otto, your interviewer

1650. Lowest Common Ancestor of a Binary Tree III​

1650

Lowest Common Ancestor of a Binary Tree III

LeetCode
Medium

Climb to Root, then DFS (Recursive)

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
top ↑
Otto, your interviewer

1257. Smallest Common Region​

1257

Smallest Common Region

LeetCode
Medium

Ancestor Set

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
top ↑

Binary search tree​

Otto, your interviewer

235. Lowest Common Ancestor of a Binary Search Tree​

235

Lowest Common Ancestor of a Binary Search Tree

LeetCode
Medium

DFS (Recursive)

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
top ↑

Finding the targets first​

Otto, your interviewer

1123. Lowest Common Ancestor of Deepest Leaves​

1123

Lowest Common Ancestor of Deepest Leaves

LeetCode
Medium

DFS (Recursive, Two Passes)

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
top ↑
Otto, your interviewer

865. Smallest Subtree with all the Deepest Nodes​

865

Smallest Subtree with all the Deepest Nodes

LeetCode
Medium

DFS (Recursive, Two Passes)

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
top ↑

The constraint matrix, side by side:

ProblemBoth exist?Root given?How many?What the extra structure buys
236 LCA of a Binary Treethe hub2Nothing - plain binary tree, counting is the only option
1644 LCA of a Binary Tree IIfrom 236either may be absent2Nothing extra; the counting answer from 236 must also prove both nodes were actually found
1676 LCA of a Binary Tree IVfrom 236all k are in the treekgiven as a listNothing extra; 236's counting rule with 2 replaced by len(nodes)
1740 Find Distance in a Binary Treefrom 2362Nothing 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
1650 LCA of a Binary Tree IIIfrom 236only p and q, each with a .parent pointer2Parent pointers turn the tree walk into a linked-list problem
1257 Smallest Common Regionfrom 1650no tree at all - only rows of [region, ...sub-regions]2Nothing until you build it - inverting the rows into a {child: parent} map recreates 1650
235 LCA of a Binary Search Treefrom 2362BST ordering tells you which child to descend into without counting anything
1123 LCA of Deepest Leavesfrom 1676but which nodes they are is withheld?however many sit on the deepest level - computed, not givenNothing extra; 1676's counting rule with the membership test replaced by depth == max_depth
865 Smallest Subtree with all the Deepest Nodesfrom 1123same as 1123same as 1123Same as 1123, asked as a subtree instead of an ancestor
On this page