🌳 Blog 4: Lowest Common Ancestor (LCA) Pattern in Binary Trees

🔍 Why This Pattern Matters?

The Lowest Common Ancestor (LCA) is a fundamental tree problem where you need to find the lowest (deepest) node in the tree that has both given nodes as descendants.
This is one of the most reusable patterns in interviews, often appearing in many variations (in Binary Tree, BST, K nodes, distance between nodes, etc.).

Once you master LCA, a whole class of problems feels simple.

---

🛠 Core Idea / Template

1. Binary Tree (General):

• Recurse into left and right subtrees.
• If both sides return non-null, current node = LCA.
• If one side is null, return the other side.

   class Solution {
       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;
           return left != null ? left : right;
       }
   }

1. Binary Search Tree (BST):

• Use property: p < root < q.
• If both p and q are smaller → go left.
• If both greater → go right.
• Else root is LCA.

   class Solution {
       public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           while (root != null) {
               if (p.val < root.val && q.val < root.val) {
                   root = root.left;
               } else if (p.val > root.val && q.val > root.val) {
                   root = root.right;
               } else {
                   return root;
               }
           }
           return null;
       }
   }

---

✅ Classic Problems

1. LCA in Binary Tree (LeetCode 236)

• Use general recursive template (above).
• Trick: Works even if tree is not BST.

---

2. LCA in BST (LeetCode 235)

• Uses BST property (O(log N) instead of O(N)).
• Best when interviewer specifies BST.

---

3. Distance Between Two Nodes

• Formula:

  dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, lca(u, v))

• Steps:

1. Find lca(u, v).
2. Use DFS to compute distance from root to any node.
3. Apply formula.

---

4. Nodes on Path Between Two Nodes

• Get LCA.

• Collect path:

  • From u → LCA.
  • From v → LCA.

• Merge them (avoiding duplicate LCA).

---

🚀 Advanced Variations

1. LCA of K Nodes (not just 2):

• Generalize by recursive reduction: LCA of (a, b, c, d) = LCA(a, LCA(b, LCA(c, d))).

1. LCA in Tree with Parent Pointers:

• Store visited ancestors of one node in a set.
• Traverse other node’s parents until first match.

1. LCA in DAG (Directed Acyclic Graph):

• Much harder (not covered in interviews unless senior).

---

🎯 Quick Pattern Checklist

• ✅ If general Binary Tree → use recursive divide & conquer.
• ✅ If BST → use value-based traversal.
• ✅ If asked about distance/path → use LCA + DFS distance.
• ✅ If multiple nodes → reduce step by step using pairwise LCA.

---

🔥 Key Takeaway:
Once you have the LCA tool in your arsenal, you can derive multiple tree distance/path problems in 2-3 lines of logic. This is a must-know pattern for FAANG interviews.

---