LCA of Binary Tree
Mahabharata — The Common Ancestor — The Earliest Shared Lineage of Two Warriors
दो योद्धाओं का साझा पूर्वज — सबसे निकट। Left और Right से उत्तर — दोनों हों तो मूल ही LCA॥
*Two warriors' closest common ancestor — nearest shared lineage. If answers come from both left and right — the current root is the LCA.*
The Story
Find the Lowest Common Ancestor (LCA) of two nodes p and q in a binary tree.
For tree `[3,5,1,6,2,0,8,null,null,7,4]`, p=5, q=1: LCA=3. For same tree, p=5, q=4: LCA=5 (a node can be an ancestor of itself).
**Recursive algorithm:** - If root is null, p, or q: return root - Recurse left and right - If both return non-null: root is the LCA (p and q found in different subtrees) - If only left non-null: return left (both p and q are in left subtree) - If only right non-null: return right
```java public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; // Base TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; // p in left, q in right return left != null ? left : right; // Both in one subtree } ```
Trace p=5, q=1 in `[3,5,1,...]`: - At 3: left=LCA(left=5 subtree, p=5, q=1). right=LCA(right=1, p=5, q=1) - LCA(5-subtree, p=5, q=1): root=5==p → return 5. left=5. - LCA(1, p=5, q=1): root=1==q → return 1. right=1. - left=5, right=1: both non-null → return root=3 ✓
Trace p=5, q=4 in `[3,5,1,6,2,0,8,null,null,7,4]`: - At 3: left=LCA(5-subtree,5,4). right=LCA(1-subtree,5,4). - LCA(5-subtree,5,4): root=5==p → return 5. left=5. - LCA(1-subtree,5,4): 5 and 4 not in this subtree → return null. right=null. - left=5, right=null → return 5 ✓
The Parent-Map Approach
BFS to build parent map. Find all ancestors of p using parent pointers. Walk q's ancestors until one is in p's ancestor set. O(n) time.
// Parent map approach:
Map<TreeNode,TreeNode> parent = new HashMap<>();
// BFS to fill parent map
// Find all ancestors of p
Set<TreeNode> pAncestors = new HashSet<>();
TreeNode cur = p; while (cur != null) { pAncestors.add(cur); cur=parent.get(cur); }
// Walk q's ancestors
cur = q;
while (!pAncestors.contains(cur)) cur = parent.get(cur);
return cur;The Post-Order Bubble-Up LCA Wisdom
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;
}Step-by-Step Walkthrough
p=root, q=root.left Base: root==p → return root. left=root (the p node). At parent: left=p, right=null → return left=p = LCA ✅
Deep Insight
**The 'bubble up' insight:** When p or q is found, it's 'returned up' the call stack. At some ancestor, one side returns p (or an LCA) and the other returns q (or an LCA). That ancestor is the LCA.
**If p is an ancestor of q:** When we reach p, we return p immediately WITHOUT descending into p's subtree (because we found p first). But q is in p's subtree! This still works because p IS the LCA (a node is its own ancestor).
**For BST (LCA in BST):** Use the BST property: - If both p,q < root.val: go left - If both p,q > root.val: go right - Otherwise: current node is LCA This is O(h) instead of O(n).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Parent map BFS + ancestor sets |
| Optimal | O(n) | O(h) | Single DFS pass, O(h) call stack |
Pattern Recognition
✅ LCA of binary tree: post-order bubble-up ✅ Base: null/p/q → return root ✅ Both subtrees return non-null → LCA is current root ✅ Only one non-null → LCA is in that subtree **LeetCode Trigger Phrases:** → "lowest common ancestor of a binary tree" → Find LCA of two nodes → Post-order with null-propagation pattern
Bhagavad Gita 11.43
पितासि लोकस्य चराचरस्य त्वमस्य पूज्यश्च गुरुर्गरीयान्।
You are the Father of all this world, of the moving and the unmoving; You are the most venerable Teacher, most worthy of worship.
Connection: The LCA is the deepest common ancestor — the first point in the lineage where two branches join into one. Like Krishna as the Father of all creation (the universal LCA from which all branches emanate), the LCA algorithm searches for that precise ancestor where the two family lines diverge. When the search finds p in one subtree and q in another, the current node is recognized as their meeting point — the deepest shared origin.