Leetcode 1650. Lowest Common Ancestor of a Binary Tree III

Let's understand what we're being asked to do. We have a binary tree with nodes, and we're given two specific nodes p and q somewhere in this tree. We need to find their lowest common ancestor (LCA).

What is a common ancestor? It's a node that has both p and q as descendants (a node can be a descendant of itself). The lowest common ancestor is the deepest such node in the tree.

Let's trace through an example: Consider a tree where node 5 has left child 3 and right child 7. Node 3 has children 2 and 4. If p=2 and q=4, their LCA is 3 (both are descendants of 3, and 3 is the lowest such node). If p=2 and q=7, their LCA is 5 (the root).

Important property: In a binary tree, every pair of nodes has exactly one LCA. The LCA could be one of the nodes itself (if one node is an ancestor of the other).

Edge cases to consider: What if p or q is the root? What if one node is a direct ancestor of the other? What if the tree has only one or two nodes?

When traversing down from the root, the LCA is the first node where the paths to p and q diverge. Before this point, both nodes are in the same subtree. After this point, they're in different subtrees.

Alternatively, if we're at a node and p is in the left subtree while q is in the right subtree (or vice versa), then this current node must be the LCA.

This observation means we can solve this recursively: for any node, check if p and q are in different subtrees. If they are, we've found the LCA. If both are in the same subtree, recurse into that subtree.

We don't need to store paths or do multiple traversals - a single traversal can identify the split point!

Think of a family tree where you're looking for the most recent common ancestor of two people. You start from the oldest ancestor and work down.

At each generation, you ask: 'Are these two people in different branches of the family?' The first time you answer 'yes', you've found the most recent common ancestor. If they're always in the same branch, keep going deeper until you find where they split (or until you reach one of them).

Use recursive depth-first search to traverse the tree. At each node, recursively search for p and q in the left and right subtrees. If the current node is p or q, return it. If both left and right recursive calls return non-null values, it means p and q are in different subtrees, so the current node is the LCA. If only one side returns non-null, propagate that result upward. This approach finds the LCA in a single traversal by identifying where the paths to p and q diverge.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def lowest_common_ancestor(root, p, q):
    """
    Find the lowest common ancestor of two nodes in a binary tree.
    Uses recursive DFS to find where paths to p and q diverge.
    """
    # Base case: if root is None or matches p or q, return root
    if root is None or root == p or root == q:
        return root
    
    # Recursively search left and right subtrees
    left_result = lowest_common_ancestor(root.left, p, q)
    right_result = lowest_common_ancestor(root.right, p, q)
    
    # If both left and right return non-null, current node is LCA
    if left_result and right_result:
        return root
    
    # Otherwise, return whichever side found a node (or None)
    return left_result if left_result else right_result

• Two-pointer convergence pattern: When nodes have parent pointers, treat the tree traversal like finding the intersection of two linked lists - move both pointers upward simultaneously, and when one reaches null, redirect it to the other's starting node to equalize path lengths and guarantee convergence at the LCA.
• Path length equalization technique: The key insight is that by swapping pointers to opposite starting nodes after reaching null, both pointers traverse the same total distance (heightP + heightQ), automatically handling trees of different depths without explicitly calculating heights first.
• Parent pointer exploitation: Unlike traditional LCA problems requiring root access and recursion, having parent pointers transforms this into a simpler iterative problem - recognize that upward traversal from nodes creates paths that must intersect at the LCA, similar to linked list cycle detection.
• Null handling pitfall: A common mistake is not handling the case where p or q is null, or stopping iteration when only one pointer is null - always continue until both pointers reference the same node, as the swap mechanism requires both to complete their paths.
• Space-efficient traversal: This solution achieves O(1) space complexity by using only two pointers instead of storing entire paths in sets or arrays - whenever you can traverse with parent/next pointers, prefer iterative pointer manipulation over path storage for better memory efficiency.
• Graph cycle detection generalization: This technique extends beyond trees to any graph intersection problem where you need to find meeting points of two paths - the pointer-swapping approach works for detecting cycles, finding merge points in linked lists, or identifying common ancestors in any hierarchical structure with upward references.