Lowest Common Ancestor of a Binary Tree

Solving tips

No BST ordering here, so you must search: use a single post-order recursion that bubbles up found targets. O(n) time, O(h) space.
Define dfs to return p or q if the node is one of them, else the node itself if BOTH child calls return non-null, else whichever single child call is non-null (left or right).
The first node whose left and right calls both return non-null is the deepest common ancestor — post-order guarantees deepest-first.
Pitfall: don't forget the 'left or right' fallback (dropping it loses a found target), and compare by node identity (is), not by value; don't try to steer by value comparison (that's the BST variant).

Problem

Given the root of a binary tree (no ordering property this time) 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 sits inside p’s subtree, the answer is p. All values are distinct.

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 property — you cannot steer by comparing values.
Expected: a single O(n) traversal; nodes have no parent pointers.

Think about it first

Hint 1

If you knew, for each subtree, whether it contains `p` or `q`, how would you recognize the LCA node?

Hint 2

The LCA is the deepest node where the two targets appear in *different* places: one in the left subtree and one in the right — or the node itself is one target and its subtree holds the other.

Hint 3

Write a recursion that returns: `p` or `q` if the current node is one of them, else whichever child call returned non-null (or the node itself if *both* children returned non-null). That single postorder pass is the whole answer.

TL;DR

One postorder recursion that bubbles up found targets — O(n) time, O(h) space.

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

Without an ordering property we must search for p and q. The direct idea: DFS to build the root-to-p path and the root-to-q path, then 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

class Solution:
    def lowestCommonAncestor(
        self, 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. It passes the constraints, but it traverses the tree twice and materializes paths it only needs for a prefix comparison — the single-pass version below does the same comparison implicitly.

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

The insight: define dfs(node) to return a non-null node exactly when node’s subtree contains p or q — returning p/q itself if only one is present, and returning the LCA once both have been seen. Then at each node: if the left call and right call 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 — exactly the LCA.

# 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':
        if root is None or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

Walkthrough on root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4: the call at 5 hits the base case (root is p) and returns 5 immediately — note 4 inside its subtree is never even visited, which is fine: since q is guaranteed to exist and wasn’t found elsewhere, it must be under 5. Back at 3: left call returned 5, right call (subtree of 1) returns None, so 3 passes 5 upward — final answer 5.

For p = 5, q = 1: left of 3 returns 5, right returns 1, both non-null → return 3.

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

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

The insight: if every node knew its parent, LCA becomes the classic “intersection of two linked lists” problem: record p’s ancestor chain in a set, then walk up from q until you hit a node already in the set. We 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

class Solution:
    def lowestCommonAncestor(
        self, 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 on p = 5, q = 4 in the example tree: DFS fills the parent map until both targets are seen. Ancestors of 5 = {5, 3}. Walking up from 4: 4 → 2 → 5 — 5 is in the set, return 5.

Complexity: O(n) time, O(n) space for the parent map. Worse on 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 robust 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? which?”), and let the first node where children’s summaries combine be the answer. This bubble-up shape recurs in diameter, tree DP, and every “lowest/deepest X” problem.