Lowest Common Ancestor of a Binary Tree

"Lowest common ancestor" sounds like theory, but it is a practical question. In a company org chart it is the most junior manager both employees report to. In a file system it is the deepest folder containing both files. In version control, git merge-base finds the lowest common ancestor of two commits.

The one-pass solution is only six lines, and it is one of the most elegant in tree interviews — but it is hard to derive if you have not seen it. This lesson builds up to it from two simpler ideas, so you can explain why it works instead of reciting it.

The problem

Given the root of a binary tree and two nodes p and q that are both in the tree, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as being in its own subtree, so a node can be the ancestor of itself.

          10        /    \       4      7      / \      \     1   9      12        / \       3   8

• p = 3, q = 1 → node 4. 3 is under 4's right side and 1 is under 4's left side.
• p = 9, q = 3 → node 9. 3 is inside 9's subtree, and 9 is its own ancestor.
• p = 1, q = 12 → node 10, the root.

Constraints: 2 ≤ n ≤ 10⁵ nodes; p and q are different nodes and both exist in the tree. The tree is not a search tree — values are in no particular order.

Clarifying questions

• Are both nodes guaranteed to be in the tree? Yes. (The one-pass solution relies on this; see the follow-ups.)
• Are we given node objects or values? Node objects. Compare with is, since values may repeat.
• Can one node be the ancestor of the other? Yes, and then the answer is that node.
• Is it a BST? No. If it were, there is a faster method — see the follow-ups.

Approach 1: the simple way — walk down while both are on one side

Start at the root. If both targets are in the left subtree, the answer is further left; if both are in the right subtree, it is further right. The first node where they split — or where the node is one of the targets — is the answer.

1def contains(node: Optional[TreeNode], target: TreeNode) -> bool:2    """True if target is somewhere in the subtree rooted at node."""3    if node is None:4        return False5    return node is target or contains(node.left, target) or contains(node.right, target)678def lca_brute(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:9    """Walk down while both targets are on the same side."""10    node = root11    while True:12        if node is p or node is q:13            return node14        p_left, q_left = contains(node.left, p), contains(node.left, q)15        if p_left and q_left:16            node = node.left17        elif not p_left and not q_left:18            node = node.right19        else:20            return node                   # the targets split here

The idea is exactly right; the cost is not. Every step down calls contains, which searches a whole subtree. On a chain of n nodes with both targets near the bottom, that is n steps each searching up to n nodes: O(n²), or about 5 × 10⁹ at n = 10⁵. The same subtrees are searched again and again.

Approach 2: compare the two root-to-node paths

Find the path from the root to p and the path from the root to q. Both start at the root and share a prefix; the last node they share is the answer.

1def lca_paths(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:2    """Record each target's root-to-node path; the last shared node wins."""3    def path_to(node: Optional[TreeNode], target: TreeNode, path: list[TreeNode]) -> bool:4        if node is None:5            return False6        path.append(node)7        if node is target or path_to(node.left, target, path) or path_to(node.right, target, path):8            return True9        path.pop()                        # target is not below here: undo10        return False1112    path_p: list[TreeNode] = []13    path_q: list[TreeNode] = []14    path_to(root, p, path_p)15    path_to(root, q, path_q)16    answer = root17    for a, b in zip(path_p, path_q):18        if a is not b:19            break20        answer = a21    return answer

For p = 3, q = 1: the paths are 10 → 4 → 9 → 3 and 10 → 4 → 1. They agree on 10 and 4, then split, so the answer is 4.

This is O(n) time — two searches and one comparison — and O(h) space for the paths. It is a perfectly good answer. The next approach does the same work in a single walk, without storing paths.

The key insight

Let each call report upward what it found in its subtree: p, q, or nothing. Then a node can decide the answer from its children's reports.

• If the left and right subtrees each report a target, the targets are on opposite sides of this node. This node is where they split: it is the LCA.
• If only one side reports something, pass that report up unchanged. It is either a target (the other one is elsewhere) or an LCA already found lower down.
• If the node is p or q, report itself immediately, without searching below. Why is that safe? If the other target is below this node, this node is the LCA and the report is already correct. If the other target is elsewhere, the split happens higher up and this report is exactly what that ancestor needs.

That last point is the subtle one. Because both targets are guaranteed to exist, "I found one target" and "I am the answer" can be the same report.

Approach 3: one recursive pass

1def lowest_common_ancestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:2    """Deepest node with both p and q in its subtree (both must be in the tree)."""3    if root is None or root is p or root is q:4        return root                       # empty, or found one of the targets5    left = lowest_common_ancestor(root.left, p, q)6    right = lowest_common_ancestor(root.right, p, q)7    if left and right:8        return root                       # one target on each side: we are the split9    return left or right                  # pass up whatever was found, if anything

Dry run: p = 3, q = 1

Calls finish in this order:

Node 4 sees 1 on its left and 3 on its right, so it returns itself. The root receives 4 from the left and nothing from the right, so it passes 4 up. The answer is 4. For p = 9, q = 3, the call on 9 returns immediately — it is a target — and 3 is never visited; the answer 9 is correct because 3 is inside 9's subtree.

Complexity. Time is O(n): each node is visited at most once. Space is O(h) for the recursion — O(log n) balanced, O(n) for a chain. For a chain deeper than Python's recursion limit, go iterative: fill a parent dictionary with an explicit stack until both targets are in it, put every ancestor of p in a set, then walk up from q until you reach one. That is O(n) time and O(n) space, with no recursion.

Edge cases

• One target is the ancestor of the other. Returns the upper target without visiting the lower one. Correct only because both are guaranteed present.
• The answer is the root. p = 1, q = 12: left reports 1, right reports 12, so the root returns itself.
• Duplicate values. The code compares node identity with is, so two nodes both holding 5 are never confused.
• Two-node tree. The root is one of the targets, so it is returned at once.

Saying it in the interview

Follow-ups

• "The tree is a binary search tree." Use the ordering: if both values are smaller than the current node, go left; if both are larger, go right; otherwise this node is the split. O(h) time and O(1) space, no recursion.
• "Each node has a parent pointer, and you are not given the root." Walk up from both nodes. It is the same problem as finding where two linked lists meet: equalise the depths, then step both up together until they meet. O(h) time, O(1) space.
• "Find the LCA of many nodes." Same recursion with a set of targets: return the node if it is in the set; the split rule is unchanged.