1123 · Lowest Common Ancestor of Deepest Leaves

LCA where the targets are not given. You must discover them and locate their ancestor in the same pass, which means returning a pair — (depth, node) — and letting the deeper side win. Sub-variants C and G composed.

1 — The problem

Find the LCA of all the deepest leaves. LC 236 cannot be used directly: it needs p and q, and here you do not know which leaves are deepest until the tree has been measured.

The two-pass solution is legitimate — measure the depth, collect the leaves at that depth, then fold LC 236 over them. The one-pass solution is better and shorter, and it comes from noticing that a single recursion can carry both facts upward at once:

The tie is the entire insight. If both subtrees are equally deep, the deepest leaves live on both sides, so their common ancestor must be this node — exactly the split-point reasoning from LC 236, expressed as a depth comparison instead of a null check.

2 — A pair travelling up

The deepest leaves are 7 and 4, both at depth 3, and their LCA is 2. Watch node 2 tie at depth 1 on both sides and claim itself, then watch that answer relay upward through 5 and 3 without changing.

Node 1 also ties — its children 0 and 8 are both leaves — so it claims itself as the LCA of the deepest leaves in its own subtree. That answer is then discarded at the root, because the left side came back deeper. Every node computes a locally correct answer; only the winning chain survives.

2.1 Why the tie must be ==, and the leaf case

• A leaf has L.depth == R.depth == 0, so it ties and returns (1, itself). That is right: the LCA of the single deepest leaf in a one-node subtree is that leaf. No special case needed.
• A node with one child never ties — one side is 0 and the other is at least 1 — so it relays. Also right: the deepest leaves are all on the one side.
• Writing >= instead of == in the tie test would make every node claim itself whenever the left is at least as deep, and the answer collapses to the root.

The base case returning (0, null) matters too: the depth must be 0 so leaves tie, and the node must be null so it is never mistaken for a real answer — though in practice a tie at depth 0 always overwrites it anyway.

2.2 Returning more than one number

This is the second problem in the pattern where the return value is a compound — 1372 (Longest ZigZag) is the other, and sub-variant K is built entirely out of them:

In Java, use a small record, an int[], or a private static class. Avoid returning two values through a field plus a return — that is the sub-variant C idiom, and it does not compose when both values are per-subtree.

3 — Complexity and edge cases

• Time O(n), space O(h). One postorder pass, O(1) per node. The two-pass version is also O(n) but walks the tree three times.
• Single node: itself — it ties at depth 0 and returns (1, itself).
• Perfect tree: the root, since every node ties all the way up.
• A straight line: the single deepest leaf, relayed up unchanged the entire way.
• Two deepest leaves that are siblings: their parent, found by the tie at that parent — the case in the visualizer.
• Common bug: comparing depths but relaying the wrong side's node. The ? : must select node and depth from the same side.
• Common bug: returning (depth + 1, nd) in the relay branches too. Then every node claims itself and the answer is always the root.

4 — Reference implementation

private record Res(int depth, TreeNode node) {}

public TreeNode lcaDeepestLeaves(TreeNode root) {
    return go(root).node();
}

private Res go(TreeNode nd) {
    if (nd == null) return new Res(0, null);
    Res L = go(nd.left), R = go(nd.right);
    if (L.depth() == R.depth())                      // tie → both sides hold deepest leaves
        return new Res(L.depth() + 1, nd);
    return L.depth() > R.depth()                     // otherwise relay the deeper side
         ? new Res(L.depth() + 1, L.node())
         : new Res(R.depth() + 1, R.node());
}

Strip the node component and this is LC 104. The LCA rides along for free on a measurement you were making anyway — which is the general shape of every sub-variant C and K solution.