LCA Deepest Leaves LeetCode 1123 Guide

LeetCode 1123 — Lowest Common Ancestor of Deepest Leaves — gives you the root of a binary tree and asks you to return the lowest common ancestor (LCA) of all its deepest leaves. A leaf is a node with no children, and the deepest leaves are those at the maximum depth in the tree.

If there is only one deepest leaf, the answer is that leaf itself. If multiple leaves share the maximum depth, you must return their lowest common ancestor — the deepest node that is an ancestor of all of them. The LCA of a node with itself is itself.

Constraints allow up to 1000 nodes with values in [1, 1000] and all values unique. The key insight is that this problem simultaneously requires finding the maximum depth and the LCA, which makes a combined post-order DFS returning both pieces of information the natural approach.

The approach uses a single post-order DFS that returns a (node, depth) pair from each subtree. For every node, we recursively compute the result from its left and right subtrees. Each result contains the candidate LCA node and the maximum depth reachable in that subtree.

The comparison is simple: if the left subtree max depth equals the right subtree max depth, the deepest leaves are on both sides, so the current node is their LCA. If the depths are unequal, all deepest leaves are on the deeper side, so we propagate that subtree's (node, depth) result upward with depth incremented by one.

This design elegantly combines two problems into one traversal. We never need to find the max depth first and then run a separate LCA pass. A single bottom-up traversal computes both simultaneously, achieving O(n) time and O(h) space where h is the tree height.

The dfs(node) function is defined recursively. The base case returns (null, 0) for a null node — a null subtree contributes no leaves and has depth 0. For a leaf node, both child calls return (null, 0), so left depth equals right depth (both 0), meaning the leaf is its own LCA candidate returned as (node, 1).

The recursive structure ensures that every subtree result is computed from its children before the parent makes a decision. Post-order processing (left, right, then current) is essential: the current node can only determine whether it is the LCA after both subtrees have reported their maximum depths.

The depth returned is always one more than the maximum child depth, representing the depth contribution of the current subtree. This depth is relative within the subtree, but the comparison between left and right depths at each node correctly identifies the split point where deepest leaves diverge.

When both subtrees return the same maximum depth, it means the deepest leaves in the left subtree are at the same level as the deepest leaves in the right subtree. Since deepest leaves exist on both sides of the current node, the current node is the lowest point where they share a common ancestor — any deeper ancestor would only cover one side.

When depths are unequal, all deepest leaves are confined to whichever subtree is deeper. The LCA of those leaves is already captured in the result returned by the deeper subtree. The current node is not their LCA because it has no deepest leaves on the shallower side — the LCA only climbs up when forced to span both sides.

This logic is depth-first and self-correcting: at every node, the comparison determines whether to promote the current node as a new LCA candidate or pass through the existing candidate from the deeper side. The final answer at the root is the LCA of all deepest leaves.

Consider the tree [3,5,1,6,2,0,8,null,null,7,4]. Node 3 is the root; its children are 5 (left) and 1 (right). Node 5 has children 6 and 2; node 1 has children 0 and 8. Node 2 has children 7 and 4. The deepest leaves are 7 and 4, both at depth 4.

DFS on the right subtree (node 1): node 0 and node 8 are leaves at depth 1 each. Left (0) depth = right (8) depth = 1, so dfs(1) returns (node 1, 2). DFS on the left subtree (node 5): dfs(6) returns (6, 1), dfs(2) returns (2, 3) because 7 and 4 are equal depth under node 2. In dfs(5): leftDepth=1, rightDepth=3, so right is deeper — returns (node 2, 4).

Back at root (node 3): left result is (node 2, 4), right result is (node 1, 2). Left depth 4 > right depth 2, so dfs(3) returns (node 2, 5). The answer is node 2, which is the LCA of leaves 7 and 4.

In Python, define dfs as a nested function returning a tuple (TreeNode, int). Base case: if not node, return (None, 0). Recursive case: left = dfs(node.left); right = dfs(node.right). Compare left[1] and right[1]: if equal return (node, left[1]+1); if left > right return (left[0], left[1]+1); else return (right[0], right[1]+1). The answer is dfs(root)[0]. Total: ~12 lines.

In Java, define a helper method returning an int[] array of size 2 where index 0 is the node's val and index 1 is the depth, or alternatively a custom Pair class. A cleaner Java approach uses a global variable for the LCA result and a separate depth-returning int dfs. Both left and right subtree depths are compared, and when equal, the global LCA is updated to the current node. Total: ~20 lines.

Both implementations run in O(n) time — every node is visited exactly once. Space is O(h) for the recursion call stack, where h is the tree height. In the worst case (completely skewed tree), h = n, giving O(n) space. For balanced trees, h = log n, giving O(log n) space.

LeetCode 236 — Lowest Common Ancestor of Binary Tree — is the foundational LCA problem. It finds the LCA of two specific target nodes using post-order DFS that returns a node when either target is found. LeetCode 1123 builds on this with depth comparison instead of target matching. LeetCode 235 — LCA of BST — uses BST ordering properties to find LCA in O(h) without full traversal.

Diameter of Binary Tree (LeetCode 543) uses the same post-order pattern of returning the max depth from each subtree and combining at each node. Both diameter and LCA of deepest leaves are solved by returning (result, depth) pairs bottom-up, making them natural companions for understanding tree post-order recursion.

The broader family includes Maximum Depth of Binary Tree (LeetCode 104), Path Sum problems, and any tree problem requiring simultaneous tracking of depth and structural information. Recognizing the (result, depth) return pattern is a key template for advanced binary tree problems at the medium-hard boundary.