Lowest Common Ancestor of a Binary Tree

The key insight is to think about the answer from the bottom up. The LCA is the lowest node whose subtree contains both p and q. A post-order DFS returns, for every node, a single answer to its parent: the node itself if it is p or q, otherwise whichever child reported a target — and the moment both the left and right calls come back non-null, that node is the answer. Values bubble up one level per recursion, so tracking ancestor paths or parent pointers is unnecessary — the tree’s own structure does the bookkeeping.

Brute Force: Collect and Compare Paths

Time O(n)Space O(n)

Record every node’s parent with a single DFS, then walk the ancestors of q upward and compare against a set of p’s ancestors. The first common ancestor on the way up from q is the lowest common ancestor — because traveling upward from either node, the first overlap is by definition the lowest node containing both.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
        parent = {root: None}
        stack = [root]
        while stack:                     # first pass: build parent pointers
            node = stack.pop()
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        ancestors = set()
        node = p
        while node:                      # store p's path to the root
            ancestors.add(node)
            node = parent[node]

        node = q
        while node not in ancestors:     # climb from q to the first overlap
            node = parent[node]
        return node

Why this is wasteful: it needs a walk of the whole tree plus explicit ancestor paths. Building the parent table is O(n) and storing p’s path to the root costs up to O(n) space in a skewed tree — even though the recursive solution below attains the same O(n) time with only O(h) space. The recursion is simpler because the path bookkeeping is implicit in the call stack.

Single-Pass Post-Order DFS (Sentinel)

OptimalTime O(n)Space O(h)

Recurse from the root. Each call does one of two things: if the node is None, p, or q, return the node itself (that is the sentinel — it says “I found a target, or there is nothing here”). Otherwise, recurse into both children and look at their answers: if both are non-null, both targets were found in opposite subtrees, so the current node is the LCA — return it. If only one child reported a target, return that one to bubble the found node upward. If neither did, return null.

class Solution:
    def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
        if root in (None, p, q):         # base case: found a target or exhausted
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:               # both subtrees found a target
            return root
        return left or right             # bubble the one real hit (or None) up

Watch the file example, root = [3,5,1,6,2,0,8,null,null,7,4] with p = 5, q = 1 — two targets in opposite subtrees, so node 3 is the first node where both branches report a hit:

start

found ptarget hit on p sidefound qtarget hit on q sideLCAboth sides returned a targetnullsubtree found nothing

post-order: children answer first, a node bubbles its chip up once it knows both sides

1 / 6

comparingresultseencurrent

The post-order sentinel: each DFS call on a node returns the node itself when it IS p or q, and otherwise passes up whichever of its children reported a target. The lowest common ancestor is the FIRST node whose left and right calls BOTH come back non-null. Everything is decided after the children have answered — that is the post-order part. Start with p = 5 on the left and q = 1 on the right; every node is unresolved.

Then the subtle self-ancestor case, same tree but q = 4, which hides inside p = 5’s own subtree — node 5 short-circuits at the p base case and is itself the answer:

start

found ptarget hit on p sidefound qtarget hit on q sideLCAboth sides returned a targetnullsubtree found nothing

post-order: children answer first, a node bubbles its chip up once it knows both sides

1 / 7

comparingresultseencurrent

The self-ancestor case: p = 5 and q = 4, and 4 sits inside 5's own subtree. A node counts as a descendant of itself, so the LCA of 5 and 4 is 5 itself. Watch how the post-order sentinel still lands on 5 even though it never descends into 6, 2, or 4.

Why this is optimal: every node is visited exactly once and does O(1) work past its children’s answers, so time is O(n) — you cannot find the LCA without at least looking at the relevant part of the tree. Space is O(h) for the recursion stack in a balanced traversal (worst case O(n) for a skewed tree), which beats the path-collection brute force’s O(n) table. The elegant part is that the sentinel makes the recursion both the search and the bookkeeping: when both children answer, the node is guaranteed to be the lowest one containing both targets, so it is returned as-is and the answer propagates straight to the root.