Lowest Common Ancestor in a Binary Tree (LCA)

1. Why Do We Need This? (Problem Statement & Status Quo)

In hierarchical data structures like binary trees, determining relationships between nodes is a fundamental operation. One of the most frequently asked algorithmic problems in software engineering interviews is finding the Lowest Common Ancestor (LCA) of two given nodes.

• What is an Ancestor? Any node on the path from the root node down to a target node is considered an ancestor of that target node. (Note: By definition in tree problems, a node can also be considered an ancestor of itself, though standard LCA queries usually involve two distinct nodes).
• What is a Common Ancestor? A node that is an ancestor to both target nodes $p$ and $q$.
• What makes it the "Lowest"? Among all common ancestors shared by $p$ and $q$, the Lowest Common Ancestor is the one located at the greatest depth (i.e., farthest away from the root, sitting lowest down in the tree diagram).

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Family Tree and Genealogical Convergence

Imagine a large family tree where you are trying to find the closest common relative (such as a parent or grandparent) shared by two cousins.

• You start tracking the lineage of Person A by listing every ancestor going all the way up to the apex ancestor (the great-great-grandparent).
• You then track the lineage of Person B doing the exact same thing.
• When you compare both upward lists, you will find several shared ancestors (e.g., great-grandparents, grandparents). However, the very first ancestor where their distinct family lines diverge as you trace downwards from the top is their most recent common ancestor—the Lowest Common Ancestor.

3. Naive Approach: Path Storage and Comparison

To solve this programmatically, the most intuitive "brute-force" or naive strategy involves finding the path from the root to each node and comparing them.

Step-by-Step Execution of the Naive Approach

1. Find Path to Node $p$: Traverse the binary tree from the root to node $p$, storing every node visited in a list or array (e.g., Path_P).
2. Find Path to Node $q$: Traverse the binary tree from the root to node $q$, storing every node visited in a second list (e.g., Path_Q).
3. Compare Paths: Iterate through both paths simultaneously from the root downwards. As long as the nodes in both lists match, keep going. The moment they diverge, the last matching node right before the divergence is your Lowest Common Ancestor.

Example Walkthrough

Consider a binary tree with nodes: 1, 2, 3, 4, 5, 6, 7.

• We want to find the LCA of node 4 and node 7.
• Path from Root to 4: [1 -> 2 -> 4]
• Path from Root to 7: [1 -> 3 -> 7]
• Comparing both paths:
  • Root 1 matches.
  • At the next step, Path P goes to 2 while Path Q goes to 3. They diverge immediately.
  • Therefore, the last matching node is 1. The LCA of 4 and 7 is 1.

Limitations of the Naive Approach

• Time Complexity: $\mathcal{O}(N)$ where $N$ is the number of nodes, because we must traverse the tree to find node $p$, and traverse it again to find node $q$.
• Space Complexity: $\mathcal{O}(N)$ because we need extra memory arrays/lists to store the root-to-node paths for both $p$ and $q$.
• Can we do better? Yes! We can eliminate the extra space overhead entirely by performing a single recursive traversal of the tree.

4. Optimized Approach: Single-Traversal Recursive Strategy

Instead of storing paths in extra memory, we can leverage post-order traversal (Left -> Right -> Root) to explore the tree and bubble up findings from the bottom up.

Core Recursive Rules

When visiting any node during our recursive traversal, we evaluate three conditions:

1. Base Case (Null or Match):
   • If the current node is NULL, return NULL.
   • If the current node matches $p$ or matches $q$, return the current node itself.
2. Explore Subtrees:
   • Recursively search for $p$ and $q$ in the Left Subtree.
   • Recursively search for $p$ and $q$ in the Right Subtree.
3. Synthesize Results:
   • Case A (Both non-null): If both the left recursive call and the right recursive call return a valid node (meaning $p$ is found in one branch and $q$ is found in the other), the current node is the Lowest Common Ancestor. We return the current node.
   • Case B (One side null): If only one side returns a non-null node and the other returns NULL, it means both target nodes reside within that single side (or the single returned node bubbles up). We return that non-null result upwards.
   • Case C (Both null): If both sides return NULL, neither target node is present in this subtree. We return NULL.

5. Complete Flow Walkthrough

Let's trace how the optimized single-traversal algorithm finds the LCA of node 4 and node 5 in a sample tree.

          1
        /   \
       2     3
      / \   
     4   5  

1. Start at Root (1): Call lca(root, 4, 5).
   • Recurse into Left Subtree: lca(node 2, 4, 5).
     • At node 2: Recurse left to node 4.
       • At node 4: Matches target $p$ (4)! Returns node 4.
     • At node 2: Recurse right to node 5.
       • At node 5: Matches target $q$ (5)! Returns node 5.
     • Back at node 2: Left returned 4, Right returned 5. Since both are non-null, node 2 recognizes it is the split point and returns node 2 to its parent.
   • Recurse into Right Subtree: lca(node 3, 4, 5).
     • Node 3 contains neither 4 nor 5. Returns NULL.
   • Back at Root 1: Left returned 2, Right returned NULL. Since the right side is null, Root 1 simply bubbles up the left result.
   • Final Result: Node 2 is returned as the Lowest Common Ancestor.

6. Implementation Code (C++ & Java)

C++ Implementation

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case: if root is null or we found p or q
        if (root == NULL || root == p || root == q) {
            return root;
        }

        // Recursively search in left and right subtrees
        TreeNode* leftResult = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightResult = lowestCommonAncestor(root->right, p, q);

        // If p is found in one subtree and q in the other, root is the LCA
        if (leftResult != NULL && rightResult != NULL) {
            return root;
        }

        // Otherwise, return the non-null child result (or NULL if both are null)
        return (leftResult != NULL) ? leftResult : rightResult;
    }
};

Java Implementation

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null or we found p or q
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recursively search in left and right subtrees
        TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
        TreeNode rightResult = lowestCommonAncestor(root.right, p, q);

        // If p is found in one side and q in the other, current root is LCA
        if (leftResult != null && rightResult != null) {
            return root;
        }

        // Return the non-null result
        return (leftResult != null) ? leftResult : rightResult;
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Definition of LCA: The Lowest Common Ancestor is the deepest node in a tree that has both target nodes $p$ and $q$ as descendants.
• Node as its own Ancestor: In binary tree problems, if one target node is an ancestor of the other (e.g., finding LCA of node 2 and node 4 where 4 is a child of 2), the ancestor node itself (2) is correctly returned as the LCA.
• Flaws of the Naive Approach: Storing explicit root-to-node paths requires unnecessary extra space ($\mathcal{O}(N)$ auxiliary memory).
• Power of Post-Order Traversal: By inspecting left and right subtrees recursively, we can resolve LCA in a single pass bottom-up.
• The Split-Point Condition: If a node receives a non-null return from both its left child and its right child, that current node is guaranteed to be the Lowest Common Ancestor.
• Single-Side Bubbling: If one child returns NULL and the other returns a valid node, the non-null node bubbles straight up the call stack.
• Optimal Efficiency: The optimized recursive approach achieves an optimal $\mathcal{O}(N)$ time complexity and reduces auxiliary space usage to the call stack height ($\mathcal{O}(H)$).