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 nodeWhy 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) upWatch 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:
post-order: children answer first, a node bubbles its chip up once it knows both sides
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:
post-order: children answer first, a node bubbles its chip up once it knows both sides
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.