Leetcode - 236. Lowest Common Ancestor of a Binary Tree

🧭 Intuition Behind the Recursive Approach

Here’s the deal. We’re going to:

1. Start at the root
2. Ask the left and right subtrees:

“Did you find either p or q in there?”

1. If both sides return a non-null result:

🎯 That means we’ve found the split point → this is the LCA.

1. If only one side gives us a non-null:

Bubble it up — maybe the LCA is higher up the tree.

1. If neither side finds anything:

Return null.

We're not tracking paths, not using extra space, and not comparing values — just pure tree structure recursion.

---

🧪 JavaScript/TypeScript Code

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  if (root === null || root === p || root === q) return root;

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

  if (left && right) return root;
  return left ?? right;
}

---

🛠️ Dry Run (Example Tree)

Input Tree:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

Let’s find LCA of 5 and 1:

• From root 3:

  • Left returns 5
  • Right returns 1

• Both sides found a target → ✅ 3 is the LCA.

---

⏱️ Time and Space Complexity

Metric	Value	Why?
Time	O(N)	Must visit each node once
Space	O(H) (stack space)	H = height of tree (recursion stack)
→ Worst case	O(N) (if tree is skewed)
→ Best case	O(log N) (balanced tree)

---

🧘 Summary of Key Takeaways

• Don’t confuse lowest with least value
• You don’t need to track paths or store parents
• Just ask the tree recursively: “Did you find what I’m looking for?”
• Let the recursive returns bubble up the answer

---