Find the Lowest Common Ancestor (LCA) in a Binary Tree.

The Lowest Common Ancestor (LCA) of two nodes, p and q, in a binary tree is the lowest node that has both p and q as descendants (where a node can be a descendant of itself). The most common approach leverages a recursive post-order traversal.

Mechanics and Logic

The core idea is to traverse the tree, checking if the current node is p or q.

Base Cases: If the current root is None, return None. If root is p or q, return root (as it's the first ancestor found on the path from the root).

Recurse: Recursively call the function for the left and right subtrees. These calls will return p, q, or None if found in their respective subtrees.

Combine Results:

* If both the left and right recursive calls return a non-null node, it means p was found in one subtree and q in the other. Therefore, the current root is their LCA.
* If only one of the left or right calls returns a non-null node, it implies either that node is the LCA (if the other target node is not in this subtree), or one of p or q is an ancestor of the other, and the returned node is that ancestor. In this case, return the non-null result.
* If both left and right calls return None, neither p nor q were found in this subtree.

This algorithm has a time complexity of O(N), as it visits each node at most once. The space complexity is O(H) due to the recursion stack, where H is the height of the tree. This pattern is useful in data lineage tools or dependency graphs (e.g., dbt models) to find common ancestors in hierarchical structures.

Specific Cases and Optimizations

For a Binary Search Tree (BST), the LCA can be found more efficiently. Since BSTs maintain an ordered property, you can navigate by comparing p.val and q.val with root.val. If both are smaller, go left; if both are larger, go right. If one is smaller and one is larger (or one equals root.val), then root is the LCA. This can be done iteratively, achieving O(H) time complexity.

It's important to handle edge cases like p or q not existing in the tree (the algorithm would return None or the existing node if only one is found) and when p equals q (the algorithm correctly returns p as its own ancestor).

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root == p or root == q:
        return root
left_lca = lowestCommonAncestor(root.left, p, q)
    right_lca = lowestCommonAncestor(root.right, p, q)
if left_lca and right_lca:
        return root  # p and q found in different subtrees
    elif left_lca:
        return left_lca # p/q found in left, or left_lca is LCA
    else:
        return right_lca # p/q found in right, or right_lca is LCA

In the interview, also mention how to handle cases where p or q might not be present in the tree, and discuss iterative approaches using parent pointers or storing paths.