54. Lowest Common Ancestor

Problem

Ties to the escalation-hierarchy framing already used in problems 10 and 45: given an org-chart tree of teams and two specific team nodes, find their lowest common ancestor — the deepest team that has both as descendants, where a team counts as its own descendant.

p and q are guaranteed to exist in the tree and are given as actual node references, not values to search for by equality.

Source: src/54_lowest_common_ancestor.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None): ...

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: ...

# tree:      3
#          /   \
#         5     1
#        / \   / \
#       6   2 0   8
lowest_common_ancestor(root, root.left, root.right).val  # -> 3
lowest_common_ancestor(root, root.left, root.left.left).val  # -> 5

Step-by-Step Approach

1. Do a recursive DFS where the return value itself carries the answer information: None means "neither p nor q was found in this subtree," and a node means either "this node IS p or q" or "this node IS the LCA."
2. Base case: if the current node is None, or it IS p, or it IS q, return it immediately without recursing further. Stopping at p/q is safe because the problem guarantees a node counts as its own ancestor — there's no need to look inside a subtree rooted at p or q for the other one.
3. Recurse into the left and right subtrees, collecting whatever each side reports back.
4. If BOTH sides returned something non-None, that means p and q were found in different subtrees of the current node — this node is exactly the point where their paths from the root split apart, so it IS the LCA. Return the current node.
5. If only ONE side returned something non-None, that side already found either p, q, or the LCA — propagate that value up unchanged, since the current node isn't where the split happens.
6. If neither side found anything, return None — this subtree contains neither target.

The elegance here is that the same recursive call answers two different questions depending on where it's called from: at the true LCA, "both children found something" identifies the split point; everywhere else, the found node is simply relayed upward untouched. No parent pointers, no explicit path storage — the recursion's return values alone reconstruct the answer. Runtime is O(n), since in the worst case the DFS visits every node once.

Reference solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lowest_common_ancestor(root, p, q):
    # recursive DFS where the return value carries meaning, O(n) time/O(h) space
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        # p and q were found in DIFFERENT subtrees -- this node is where their paths split
        return root
    # only one side found something -- propagate it up unchanged
    return left if left else right

Key Functions & Tricks

• root is p or root is q — identity check (not value equality), and short-circuits recursion the instant either target is reached.
• Return value doubles as signal — None means "not found here," a node means "found p/q/the LCA," with no separate boolean flags.
• if left and right — both sides non-None is exactly the condition that identifies the split point (the LCA).
• left if left else right — propagates whichever single side found something, unchanged, when the current node isn't the split point.
• No parent pointers or path lists — the whole answer falls out of what recursive calls return, not extra bookkeeping.

How to Recognize This Pattern