Lowest Common Ancestor of a Binary Tree

Problem Statement

You’re a family tree historian finding the lowest common ancestor (LCA) of two nodes in a binary tree. Given the root and nodes p and q, return their LCA. This medium-level recursive quest is a lineage hunt—trace paths to unite the branches!

Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Tree:

   3
  / \
 5   1
/ \ / \
6 2 0  8
 / \
7   4

Output: 3 (LCA of 5 and 1)

Input: p = 5, q = 4

Output: 5 (5 is ancestor of 4)

Input: root = [1,2], p = 1, q = 2

Output: 1

Code

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;
    }
}
            

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == 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
            

function lowestCommonAncestor(root, p, q) {
    if (!root || root === p || root === q) return root;
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left || right;
}
            

Explanation

• DFS Insight: LCA is where paths to p and q split—found when both subtrees return nodes.
• Flow: Recurse left and right; if both return non-null, root is LCA; else, propagate non-null result.
• Example Walkthrough: [3,5,1], p=5, q=1 → left=5, right=1, root=3 is LCA.
• Edge Case: p or q is root, or one is ancestor of the other—handled naturally.
• Alternative: Store paths to p and q, find last common node—more space, same result.

Note