Core Approach

1. Base Cases:

• If the current node is null, return null
• If the current node matches either target, return the current node (a node is its own ancestor)

2. Recursive Search:

• Recursively search the left subtree, storing the result
• Recursively search the right subtree, storing the result

3. Result Analysis:

• If both left and right results are non-null → current node is the lowest common ancestor
• If only the left result is non-null → the ancestor is in the left subtree
• If only the right result is non-null → the ancestor is in the right subtree

Why Return When Finding a Target?

The core principle is that recursion propagates found markers upward.

The function's purpose must be clear: findCommonAncestor(currentNode, target1, target2)

If the subtree rooted at currentNode contains either target, return the found node. If neither target is present, return null.

Scenario 1: Current Node is a Target

When the current node matches one target, it guarantees that subtree contains that target. According to the function's responsibility, it returns itself, signaling upward: "I found the target."

Scenario 2: Current Node is the Other Target

Similarly, the function returns itself to indicate: "I found the other target."

Implementation Details

1. Node Structure: Standard binary tree node with value, left child, and right child references.

2. Recursive Logic:

• Begin traversal from the root node
• If both targets are found in different subtrees, the current node is their LCA
• If both targets are found in the same subtree, continue propagating that result upward

3. Time Complexity: O(n) - In the worst case, we traverse the entire tree once

4. Space Complexity: O(n) - Due to the recursion stack in the worst case (skewed tree)

Python Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

csSolution:
    def find_common_ancestor(self, current_node, target1, target2):
        # Base cases: null node or found a target
        if current_node is None or current_node == target1 or current_node == target2:
            return current_node
        
        # Search left subtree
        left_result = self.find_common_ancestor(current_node.left_child, target1, target2)
        # Search right subtree
        right_result = self.find_common_ancestor(current_node.right_child, target1, target2)
        
        # Case 1: Targets found in different subtrees
        if left_result and right_result:
            return current_node
        # Case 2: Only left subtree contains targets
        elif left_result:
            return left_result
        # Case 3: Only right subtree contains targets
        else:
            return right_result