Problem Summary

You are given the root of a binary tree.
Your task is to return the lowest common ancestor (LCA) of all the tree’s deepest leaves.

A deepest leaf is any node that has the maximum depth in the entire tree.

Example
Input:

      1
     / \
    2   3
   /
  4

Deepest leaf is 4, so the answer is node 4.

Another example:

        1
       / \
      2   3
     /     \
    4       5

Deepest leaves are 4 and 5; their LCA is node 1.

Constraints

• Tree nodes ≤ 1000
• Node values are unique or irrelevant; structure matters
• Must run in O(n)

---

Key Insight

This problem essentially requires:

1. Finding the maximum depth of the tree
2. Collecting all nodes at that depth
3. Computing the LCA of all these nodes

But the most efficient way is to do it in a single DFS pass.

---

Approach (Simple English)

We use a DFS function that returns two pieces of information for each node:

1. Height (depth) of the deepest leaf below this node
2. LCA of all deepest leaves in its subtree

Define a helper:

dfs(node) returns (height, lcaNode)

How it works

For each node:

• Recursively compute:
  • Left child height and LCA
  • Right child height and LCA
• Compare leftHeight and rightHeight:
  • If leftHeight > rightHeight
    Deepest leaves are on the left
    Return (leftHeight + 1, leftLCA)
  • If rightHeight > leftHeight
    Deepest leaves are on the right
    Return (rightHeight + 1, rightLCA)
  • If both heights are equal
    This node is the lowest common ancestor of deepest leaves
    Return (height + 1, currentNode)

Why This Works

• Equal depths means deepest leaves exist on both sides, so their LCA is the current node.
• Larger depth on one side means the deepest leaves are fully contained within one subtree.
• This combines depth calculation and LCA calculation in a single elegant pass.

Time Complexity

O(n), since each node is visited once.

Space Complexity

O(h), where h is tree height (recursion stack).

---

Java Code (Optimal DFS Solution)

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root).lca;
    }

    private static class Result {
        int height;
        TreeNode lca;
        Result(int height, TreeNode lca) {
            this.height = height;
            this.lca = lca;
        }
    }

    private Result dfs(TreeNode node) {
        if (node == null) {
            return new Result(0, null);
        }

        Result left = dfs(node.left);
        Result right = dfs(node.right);

        if (left.height > right.height) {
            return new Result(left.height + 1, left.lca);
        } else if (right.height > left.height) {
            return new Result(right.height + 1, right.lca);
        } else {
            return new Result(left.height + 1, node);
        }
    }
}

Notes:

• The Result class bundles the height and LCA for cleaner code.
• Height counts edges or levels; consistency is maintained throughout.

---

Dry Run

Consider:

        1
       / \
      2   3
     /
    4

DFS on node 4

Left = (0, null)
Right = (0, null)
Heights equal → return (1, 4)

DFS on node 2

Left = (1, 4)
Right = (0, null)
Left is deeper → return (2, 4)

DFS on node 3

Left = (0, null)
Right = (0, null)
Equal → return (1, 3)

DFS on node 1

Left = (2, 4)
Right = (1, 3)
Left is deeper → return (3, 4)

Final result: node 4

---

Edge Cases

• Single node tree → that node is the answer
• Deepest leaves all on one side → LCA is the deepest leaf
• Multiple deepest leaves spread across subtrees → LCA is their split point
• Empty tree → return null