Lowest Common Ancestor of a Binary Tree

Problem in plain words

You are given a binary tree (not a BST) and two distinct nodes p and q that are guaranteed to be in it. Return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as its own ancestor, so if p sits above q, the answer is p itself.

Example: root 1 with children 2 and 3; 2 has children 4 and 5. The LCA of 4 and 5 is 2, the LCA of 4 and 3 is 1, and the LCA of 2 and 5 is 2.

Intuition

Ask each subtree a simple question: "did you find p or q?" A subtree returns the found node, or null if it contains neither. If a node hears a non-null answer from both its left and its right subtree, then p and q are split across it, so it is the LCA. If only one side answers, pass that answer upward — it is either one of the targets or an LCA already found lower down. If the current node is p or q, return it immediately: anything below it cannot be a lower common ancestor.

Approach

1. If the node is null, p or q, return the node.
2. Recurse into the left subtree and the right subtree.
3. If both results are non-null, return the current node — it is the split point.
4. Otherwise return whichever result is non-null (or null if both are).

Dry run

Find the LCA of 4 and 3 in the tree above.

Java solution

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

Python solution

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 if left else right

Complexity

Edge cases and common mistakes

• One node is an ancestor of the other — the early return at p (or q) makes that node the answer, which is correct.
• Comparing values instead of nodes — compare node references (== in Java, is in Python). Values are unique here, but references are the safer habit.
• Using BST logic — this tree has no ordering, so you cannot decide a direction by comparing values; that trick only works for LeetCode 235.
• Assuming both nodes exist — this solution relies on the guarantee. If one might be missing, you need to track whether each was actually found.