Lowest Common Ancestor in a Binary Tree

1. What is the Lowest Common Ancestor (LCA)?

First, let's define what we're looking for.

Definition: The Lowest Common Ancestor (LCA) between two nodes p and q in a binary tree is the lowest (deepest) node that has both p and q as descendants. A crucial part of this definition is that a node is considered a descendant of itself.

Let's look at a few cases to make this clear.

Now, consider the case where one node is an ancestor of the other. For example, in the tree above, what is the LCA of nodes 5 and 4?

• Node 5 is an ancestor of node 4.
• Node 5 is an ancestor of itself (by our definition).
• Therefore, the lowest node that is an ancestor to both is node 5 itself.

To see these cases explained visually, the first part of the following video is very helpful.

2. The Recursive Intuition

Just like with height and diameter, a recursive DFS approach is the most elegant way to solve the LCA problem. The core idea is to traverse the tree and have our recursive function report back what it finds in its subtrees.

For any given node, our recursive function will answer the question: "Have you found p or q in the subtree rooted at this node?"

There are three key possibilities for any node we are visiting:

1. The current node is p or q. If so, we've found one of the nodes. There's no need to search deeper in this branch. This node itself is the "evidence" we need to pass back up to its parent.

2. p is in one subtree, and q is in the other. If our recursive call on the left subtree finds one of the nodes, and the recursive call on the right subtree finds the other, then the current node must be the point where the paths to p and q diverge. This makes the current node the LCA.

3. Both p and q are in the same subtree (either left or right). In this case, the recursive call on that subtree will eventually find the LCA at a deeper level and return it. Our current node should simply pass that result up to its parent.

This logic of defining a "policy" for a single node and trusting recursion to handle the rest is a fundamental skill for tree problems. The following video provides an excellent mental framework for this.

3. The Algorithm and Implementation

Now, let's translate this intuition into a concrete algorithm and Python code. Our function, lowestCommonAncestor(root, p, q), will perform a post-order traversal and return the following:

• The node p or q if it's found.
• The LCA if it's found.
• None if neither is found in the current subtree.

Here's the step-by-step logic:

1. Base Case: If the current root is None, or if it's equal to p or q, we return root. This stops the recursion for this path.
2. Recursive Step: Recursively call the function on the left and right subtrees.
   • left_result = lowestCommonAncestor(root.left, p, q)
   • right_result = lowestCommonAncestor(root.right, p, q)
3. Combine Results:
   • If left_result and right_result are both non-None, it means p was found on one side and q on the other. The current root is the LCA. Return root.
   • If only left_result is non-None, it means the LCA (or one of the target nodes) is in the left subtree. Return left_result.
   • If only right_result is non-None, do the same for the right side. Return right_result.
   • If both are None, neither node was found in this subtree. Return None.

The following article provides a clean implementation of this logic.

Here is the Python implementation for your reference:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base case: If root is None, or we found p or q, return root.
        if root is None or root == p or root == q:
            return root

        # Recursively search in left and right subtrees.
        left_result = self.lowestCommonAncestor(root.left, p, q)
        right_result = self.lowestCommonAncestor(root.right, p, q)

        # Decision logic:
        # If both subtrees returned a non-None value, then the current root is the LCA.
        if left_result and right_result:
            return root
        
        # Otherwise, the result is in whichever subtree returned a non-None value.
        # If both returned None, this expression correctly evaluates to None.
        return left_result or right_result

4. Complexity Analysis

Understanding the performance of this algorithm is crucial for competitive programming.

• Time Complexity: $O(N)$, where $N$ is the number of nodes in the tree. In the worst case, we have to visit every node once to find p and q.
• Space Complexity: $O(H)$, where $H$ is the height of the tree. This space is used by the recursion call stack. For a balanced tree, this is $O(\log N)$. For a completely skewed tree (like a linked list), the height is $N$, making the worst-case space complexity $O(N)$.

The final section of the "Cracking FAANG" video provides a concise summary of this analysis.

Conclusion

Congratulations on completing the "Binary Trees and Traversals" module! You've built a solid foundation, progressing from basic traversals to solving complex problems like finding diameter and the lowest common ancestor.

Key Takeaways:

• The LCA is the deepest node that is an ancestor to two given nodes, p and q. A node can be an ancestor of itself.
• A recursive, post-order traversal provides an elegant $O(N)$ solution.
• The recursive function's logic is key: it returns the relevant node (p, q, or the LCA) from its subtree.
• The LCA is identified at the node where the search results from the left and right subtrees first diverge.

The recursive patterns you've practiced in this module are fundamental and will reappear in many other data structures and algorithms.

Up Next:
We will now move on to the next module, "Binary Search Trees (BSTs)". BSTs are a special, ordered type of binary tree. This ordering property allows for highly efficient searching, insertion, and deletion operations, making them one of the most important data structures in computer science. Your understanding of tree traversal and recursion will be invaluable as we explore them.