The Meeting Point

[!NOTE] This module explores the core principles of the Lowest Common Ancestor (LCA) problem, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Definition

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example: Given tree: [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1. LCA is 3.

Edge Cases & Clarifying Questions

Are both nodes guaranteed to be in the tree? Yes, the problem assumes both p and q exist in the tree.
Can a node be a descendant of itself? Yes, a node is allowed to be a descendant of itself according to the definition.
What if the tree only has two nodes? One of the nodes must be the root, and thus the root is the LCA.

2. Interactive Analysis

Select two nodes (P and Q) and see where their paths merge.

Select P...

3. Intuition

The Genesis (Analogy)

Imagine finding the closest shared manager for two employees in a corporate hierarchy. If both employees start reporting up their respective chains simultaneously, the first manager who oversees both of them is the Lowest Common Ancestor.

Brute Force (Path Tracing)

The most straightforward way is to find the path from the root to node P, and the path from the root to node Q. We can store these paths in two arrays. Once we have both paths, we iterate through them simultaneously until they diverge. The last common node before divergence is the LCA.

Why it’s inefficient: It requires two full traversals to find the nodes and O(N) extra space to store the paths.

Optimized (Postorder Traversal)

Instead of storing paths, we can use a Bottom-Up approach via Postorder Traversal. The intuition is to let each subtree report back whether it contains P, Q, or both. At any node root:

If root is P or Q, return root.
Recurse Left and Right to find P and Q.
Result Evaluation:
- If both Left and Right return a non-null node, it means P is in one subtree and Q is in the other. Therefore, the current root is the split point, making it the LCA.
- If only one side returns non-null, it means both P and Q (or the one we found so far) exist in that subtree. We propagate that non-null result upwards.

Common Pitfalls

Forgetting that a node can be an ancestor of itself. If P is the parent of Q, returning P immediately upon finding it handles this naturally, as we don’t need to traverse P’s children to find Q.

4. Solutions

Java

```java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null || root == p || root == q) return root;

  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);

  if (left != null && right != null) return root; // Found split point

  return (left != null) ? left : right; // Propagate up
}
```

```go
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  if root == nil || root == p || root == q {
    return root
  }
  left := lowestCommonAncestor(root.Left, p, q)
  right := lowestCommonAncestor(root.Right, p, q)

  if left != nil && right != nil {
    return root
  }
  if left != nil {
    return left
  }
  return right
}
```

5. Complexity Analysis

Strategy	Time	Space	Notes
Brute Force (Path Tracing)	O(N)	O(N)	Two traversals to store paths in arrays, then comparing them.
DFS (Recursion)	O(N)	O(N)	We visit each node in the worst case. Space is O(N) for recursion stack (skewed tree).