Lowest Common Ancestor of Deepest Leaves: Recursive Depth Comparison

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves. If there is only one deepest leaf, return that leaf itself. This is LeetCode 1123: Lowest Common Ancestor of Deepest Leaves, and it is a clean exercise in combining depth tracking with LCA identification in a single recursive pass.

Why this problem matters

This problem sits at the intersection of two fundamental tree concepts: computing depth and finding lowest common ancestors. Most LCA problems give you two specific target nodes. This one is different -- you have to discover which nodes matter (the deepest leaves) and find their LCA, all in one traversal. The recursive pattern you learn here generalizes to any problem where you need to propagate information up from subtrees and make decisions based on comparing left and right results.

The key insight

At each node, you recursively compute the depth of the deepest leaf in the left subtree and the right subtree. Three cases arise:

1. Left depth equals right depth: Both subtrees reach the same maximum depth, so the deepest leaves exist on both sides. The current node is their LCA.
2. Left depth is greater: The deepest leaves are only in the left subtree. Pass the left subtree's answer upward.
3. Right depth is greater: The deepest leaves are only in the right subtree. Pass the right subtree's answer upward.

By returning both the candidate LCA node and the depth from each recursive call, you solve the problem in a single DFS pass.

The solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lca_deepest_leaves(root: TreeNode) -> TreeNode:
    def dfs(node):
        if not node:
            return None, 0

        left_lca, left_depth = dfs(node.left)
        right_lca, right_depth = dfs(node.right)

        if left_depth == right_depth:
            return node, left_depth + 1
        elif left_depth > right_depth:
            return left_lca, left_depth + 1
        else:
            return right_lca, right_depth + 1

    return dfs(root)[0]

The dfs function returns a tuple of two values: the LCA candidate and the maximum depth found in that subtree. When a node is None, it returns depth 0 -- the base case.

At each node, you compare the depths returned by the left and right children. If both depths match, the current node is the LCA because both subtrees contain leaves at the maximum depth. If one side is deeper, the LCA must be in that deeper side, so you pass its result upward. Either way, you add 1 to the depth before returning, since the current node adds one level.

The final answer is the first element of the tuple returned by dfs(root).

Visual walkthrough

Let's trace the algorithm on the tree [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]. Watch how depth comparisons at each node determine where the LCA lives.

The key moment is at node 2. Its left child (7) and right child (4) both return depth 3. Equal depths mean both sides contain deepest leaves, so node 2 becomes the LCA. Every ancestor above node 2 sees unequal depths and simply passes node 2 upward.

Complexity analysis

Time is O(n) where n is the number of nodes in the tree. Every node is visited exactly once during the DFS traversal, and the work at each node is O(1) -- just compare two depths and pick a result.

Space is O(h) where h is the height of the tree. This comes from the recursion stack. In the worst case (a skewed tree), h equals n. For a balanced tree, h is O(log n).

The building blocks

1. Depth-returning recursion

The core pattern is a recursive function that returns depth information from the bottom up:

def dfs(node):
    if not node:
        return None, 0
    left_lca, left_depth = dfs(node.left)
    right_lca, right_depth = dfs(node.right)
    return result, max(left_depth, right_depth) + 1

This is a generalization of computing maximum depth. Instead of returning just a number, you return a number paired with a node reference. You will see this "return a tuple from recursion" pattern in problems like Binary Tree Maximum Path Sum, Diameter of Binary Tree, and Balanced Binary Tree.

2. LCA identification by depth comparison

The decision logic at each node uses the depth comparison to decide what to propagate upward:

if left_depth == right_depth:
    return node, left_depth + 1
elif left_depth > right_depth:
    return left_lca, left_depth + 1
else:
    return right_lca, right_depth + 1

When depths are equal, the current node is the answer for its subtree. When they differ, the answer comes from the deeper side. This three-way branch is the entire decision logic of the algorithm. No extra data structures, no second pass, just a clean comparison at each node.

Edge cases

• Single node tree: The root is the only leaf and also the deepest. Return the root.
• All leaves at the same depth (complete binary tree): Every path from root to leaf has the same depth. The LCA of all deepest leaves is the root itself.
• Skewed tree (every node has only one child): There is exactly one leaf, the bottom node. That leaf is both the deepest and the LCA. The recursion naturally handles this because one side always returns depth 0.
• Two children but only one has deeper descendants: The deeper side's LCA propagates upward. The shallower side is ignored.
• Very deep tree: The recursion stack may hit limits for extremely deep trees (depth over ~1000 in Python). Iterative approaches exist but are rarely needed for this problem's constraints.

From understanding to recall

You have seen the pattern: recurse to the bottom, return depth and LCA candidate, compare depths at each node, and let equal depths identify the answer. The logic is compact and the code is short.

But in an interview, the details matter. Do you return left_depth + 1 or left_depth? Do you return node or left_lca when depths are equal? These small choices determine whether your solution is correct, and they are exactly the kind of thing that slips under pressure.

Spaced repetition locks in the details. You practice writing the recursive base case, the depth comparison, and the tuple return from memory. After a few rounds at increasing intervals, the pattern becomes automatic. You see "deepest leaves" in a problem, and the depth-comparison DFS template flows out naturally.

Related posts

• Lowest Common Ancestor of a Binary Tree - The classic LCA problem where you are given two specific target nodes
• Maximum Depth of Binary Tree - The foundational depth-computing recursion that this problem builds on
• Binary Tree Maximum Path Sum - Another problem that returns multiple values from recursion to track both a candidate answer and a propagated value

CodeBricks breaks Lowest Common Ancestor of Deepest Leaves into its depth-returning recursion and LCA-by-comparison building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree recursion problem shows up in your interview, you do not hesitate. You just write it.