Lowest Common Ancestor of a Binary Tree

Problem

Given the root of a binary tree and two nodes p and q that both exist in the tree, return their lowest common ancestor: the deepest node whose subtree contains both. A node may be its own ancestor, so if q lies inside p’s subtree, the answer is p. All values are distinct. The tree has no ordering property, so value comparisons cannot guide the search.

Examples

• Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → Output: 3 5 and 1 are the root’s two children; only 3 contains both.
• Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 → Output: 5 4 is a descendant of 5, so 5 is its own ancestor and the LCA.
• Input: root = [1,2], p = 1, q = 2 → Output: 1 The root contains both nodes; nothing deeper does.

Constraints

• 2 <= n <= 10^5 nodes; all values distinct; p != q, both guaranteed present.
• No BST ordering, so you cannot navigate by comparing values.
• Expected: a single O(n) traversal; nodes have no parent pointers.

Think about it first

TL;DR

One postorder recursion that returns found targets up the call stack — O(n) time, O(h) space.

The examples below all use this tree (root = [3,5,1,6,2,0,8,null,null,7,4]):

graph TD
    n3["3"] --> n5["5"]
    n3 --> n1["1"]
    n5 --> n6["6"]
    n5 --> n2["2"]
    n2 --> n7["7"]
    n2 --> n4["4"]
    n1 --> n0["0"]
    n1 --> n8["8"]

Approach 1 — Brute force: find both paths, compare prefixes

Without an ordering property, we must search for p and q directly. Build the root-to-p path and the root-to-q path with DFS; the LCA is the last node the two paths share.

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

def lowestCommonAncestor(
    root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
) -> 'TreeNode':
    def find_path(node: 'TreeNode', target: 'TreeNode',
                  path: List['TreeNode']) -> bool:
        if not node:
            return False
        path.append(node)
        if node is target:
            return True
        if find_path(node.left, target, path):
            return True
        if find_path(node.right, target, path):
            return True
        path.pop()
        return False

    path_p: List['TreeNode'] = []
    path_q: List['TreeNode'] = []
    find_path(root, p, path_p)
    find_path(root, q, path_q)

    lca = root
    for x, y in zip(path_p, path_q):
        if x is y:
            lca = x
        else:
            break
    return lca

Complexity: O(n) time (two full DFS passes) and O(h) space per stored path. This works, but it traverses the tree twice and stores paths only to compare their prefixes. The single-pass version below does the same comparison implicitly.

Approach 2 — Single-pass postorder recursion (the classic)

Define dfs(node) to return a non-null node exactly when node’s subtree contains p or q: it returns p or q itself when only one is present, and the LCA once both have been seen. At each node, if the left and right calls both return non-null, the targets straddle this node and it is the LCA; if only one side returns non-null, pass that result up unchanged. Because the traversal is postorder (children before the node), the first node that sees both sides non-null is the deepest such node, which is the LCA.

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

def lowestCommonAncestor(
    root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
) -> 'TreeNode':
    if root is None or root is p or root is q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

Walkthrough for p = 5, q = 4: the call at 5 hits the base case (root is p) and returns 5 immediately. Node 4 inside its subtree is never visited, which is correct: since q is guaranteed to exist and was not found elsewhere, it must lie under 5. Back at 3, the left call returned 5 and the right call (subtree of 1) returns None, so 3 passes 5 upward. Final answer: 5.

For p = 5, q = 1: the left call of 3 returns 5 and the right returns 1. Both are non-null, so 3 is the LCA.

Complexity: O(n) time (each node visited once), O(h) recursion stack.

Approach 3 — Iterative with parent pointers (the well-known alternative)

If every node knew its parent, LCA becomes the “intersection of two linked lists” problem: record p’s ancestor chain in a set, then walk up from q until you reach a node already in the set. Build the parent map with one BFS/DFS.

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

def lowestCommonAncestor(
    root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
) -> 'TreeNode':
    parent: Dict['TreeNode', Optional['TreeNode']] = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        for child in (node.left, node.right):
            if child:
                parent[child] = node
                stack.append(child)

    ancestors = set()
    node = p
    while node:
        ancestors.add(node)
        node = parent[node]
    node = q
    while node not in ancestors:
        node = parent[node]
    return node

Walkthrough for p = 5, q = 4: DFS fills the parent map until both targets are seen. Ancestors of 5 are {5, 3}. Walking up from 4: 4 → 2 → 5, and 5 is in the set, so return 5.

Complexity: O(n) time, O(n) space for the parent map. This uses more space than Approach 2, but it generalizes: with real parent pointers it needs no traversal at all, and it handles “LCA of many nodes” naturally.

Common pitfalls

• Returning early from the root call when root is p without worrying that q might not be below it — that shortcut is only valid because the problem guarantees both nodes exist in the tree.
• Writing left and right logic but forgetting the left or right fallback, which silently drops a found target on the way up.
• Comparing by node.val instead of node identity — works only because values are distinct; identity (is) is the safer habit.
• Trying to steer by value comparison — that’s the BST variant; here it gives wrong answers.

Pattern takeaway

Postorder is how information flows upward in a tree. When a question asks about the relationship between nodes deep in a tree (“deepest node such that…”), design a recursion whose return value summarizes the subtree (“did I find a target, and which one?”), and let the answer be the first node where the children’s summaries combine. The same upward-summary shape recurs in diameter, tree DP, and every “lowest/deepest X” problem.