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.

2. Interactive Analysis

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

Select P...

3. Intuition

We use Postorder Traversal (Bottom-Up). At any node root:

If root is P or Q, return root.
Recurse Left and Right.
Result:
- If Left & Right both return non-null, it means P is in one subtree and Q is in the other. Thus, root is the LCA.
- If only one returns non-null, it means both P and Q (or the one we found so far) are in that subtree. Propagate that result up.

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
DFS (Recursion)	O(N)	O(N)	We visit each node in the worst case. Space is O(N) for recursion stack (skewed tree).