LCA of Deepest Leaves
Mahabharata — The Deepest Warriors' Common Origin — Finding the Shared Root of the Farthest Leaves
सबसे गहरे पत्ते — उनका साझा पूर्वज। यदि दोनों ओर समान गहराई — यही LCA; अन्यथा गहरी ओर जाओ॥
*The deepest leaves — their common ancestor. If depth equal on both sides — this is LCA; otherwise follow the deeper side.*
The Story
Find the LCA of the deepest leaves in a binary tree. The deepest leaves are those at the maximum depth.
For tree `[3,5,1,6,2,0,8,null,null,7,4]`: deepest leaves are 7 and 4 (both at depth 4). LCA=2. For tree `[1]`: deepest leaf is 1 itself. LCA=1. For tree `[0,1,3,null,2]`: deepest leaf is 2 (depth 3). LCA=2.
**Recursive with (node, depth) pairs:** - At each node: compute (lca, depth) for left and right subtrees - If left.depth == right.depth: current node is LCA (deepest leaves split across both) - If left.depth > right.depth: LCA is from left subtree - If right.depth > left.depth: LCA is from right subtree
```java public TreeNode lcaDeepestLeaves(TreeNode root) { return dfs(root).node; }
pair dfs(TreeNode root) { if (root == null) return new pair(null, 0); pair left = dfs(root.left); pair right = dfs(root.right); if (left.depth == right.depth) return new pair(root, left.depth + 1); if (left.depth > right.depth) return new pair(left.node, left.depth + 1); return new pair(right.node, right.depth + 1); } ```
Where `pair` is a helper class `{TreeNode node; int depth;}`.
Trace `[3,5,1,6,2,0,8,null,null,7,4]`: - At 7: (7,1), at 4: (4,1), at 2: both depth=1 → (2,2) - At 6: (6,1) [leaf], at 2: (2,2). right.depth>left.depth → (2,3) - At 5: left=(2,3), right=(6,1) (should be (6,1)). Actually 6 is leaf=(6,1). left.depth=3>1 → (2,4) - At 0,8: leaves=(0,1),(8,1). At 1: both=1 → (1,2)... hmm let me re-trace properly: - At 1: left=0(leaf,1), right=8(leaf,1). Equal → (1,2) - At 3: left=(2,4), right=(1,2). left.depth>right → return (2,4). - LCA=2 ✓
The Two-Pass Approach
Pass 1: find max depth. Pass 2: find LCA of all nodes at max depth using general LCA. O(n²).
// Two-pass: find max depth, collect leaf nodes at max depth, find their LCA
// O(n) per LCA query × multiple nodes = O(n²)
// The (node,depth) single-pass is optimal.The Depth-Pair Post-Order Wisdom
public TreeNode lcaDeepestLeaves(TreeNode root) {
return dfs(root)[0];
}
TreeNode[] dfs(TreeNode root) {
if (root == null) return new TreeNode[]{null, new TreeNode(0)};
// Use int[] {lca_id, depth} — but TreeNode for lca:
// Returns [lca, depthNode] — easier with a helper class
// Simplified inline version:
int[] info = new int[1]; // depth holder
return new TreeNode[]{solve(root, info), new TreeNode(info[0])};
}
// Clean version with pair
public TreeNode lcaDeepestLeavesClean(TreeNode root) {
int[] res = helper(root);
return nodeOf(root, res[0]); // find node by value — not clean
// Better: return TreeNode from helper directly
return helperNode(root);
}
private int maxDepth = 0;
private TreeNode result;
public TreeNode lcaDeepestLeavesV2(TreeNode root) {
dfsV2(root, 0);
return result;
}
int dfsV2(TreeNode root, int depth) {
if (root == null) return depth;
int left = dfsV2(root.left, depth + 1);
int right = dfsV2(root.right, depth + 1);
if (left == right && left >= maxDepth) { maxDepth = left; result = root; }
return Math.max(left, right);
}Step-by-Step Walkthrough
Tree=[1]: dfs(1)=leaves on both sides are null(depth 0) → equal → (1, 1). LCA=1 ✅
Deep Insight
**The depth-comparison insight:** If the deepest leaves are in both left and right subtrees (equal max depths), the current node is their LCA. If they're all in one subtree, recurse into that subtree.
**Single-pass O(n):** The (node, depth) pair approach solves both 'what's the max depth' and 'what's the LCA' in a single post-order pass.
**Related:** tr-12 (LCA of specific nodes), tr-14 (LCA in BST). This is LCA of dynamically determined nodes (all deepest leaves).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Two passes + LCA queries |
| Optimal | O(n) | O(h) | Single post-order pass returning (lca, depth) |
Pattern Recognition
✅ LCA deepest leaves: single-pass (node, depth) post-order ✅ Equal depths at current node → current is LCA ✅ Unequal → return LCA from deeper side ✅ Returns (lca_node, max_depth_in_subtree) **LeetCode Trigger Phrases:** → "LCA of deepest leaves" → Find common ancestor of deepest nodes → Post-order with depth tracking
Bhagavad Gita 18.18
ज्ञानं ज्ञेयं परिज्ञाता त्रिविधा कर्मचोदना। करणं कर्म कर्तेति त्रिविधः कर्मसङ्ग्रहः॥
Knowledge, the object of knowledge, and the knower — these three motivate action. Instrument, action, and doer — these three constitute action.
Connection: The LCA of deepest leaves requires three pieces of information: the LCA node, the depth, and the current traversal position — a triad that motivates the algorithm's structure. Like the Gita's teaching on the three constituents of action, the algorithm returns both the result (LCA) and the depth simultaneously, using this dual knowledge to determine whether the deepest leaves converge at the current node or diverge into deeper territory.