Smallest Subtree with all the Deepest Nodes: Bottom-Up Depth Comparison

You are given the root of a binary tree. Return the smallest subtree such that it contains all of the deepest nodes in the tree. A node is called the deepest if it has the largest depth possible among any node in the entire tree.

This is LeetCode 865: Smallest Subtree with all the Deepest Nodes, and it is a beautiful example of how comparing left and right subtree depths can solve a problem that initially feels complicated. The trick is that you never need to find the deepest nodes first. You find them and the answer simultaneously, in a single pass.

Why this problem matters

This problem teaches you one of the most versatile patterns in tree recursion: returning a tuple of (node, depth) from your recursive function. Instead of just returning a single value like depth or a boolean, you bundle two pieces of information together and let the parent make a decision based on both.

You will see this pattern again in problems like Binary Tree Maximum Path Sum and Diameter of Binary Tree, where the recursive function returns one thing but the answer depends on combining information from both subtrees. Once you internalize the idea of "compare left and right depths, then decide," a whole family of tree problems becomes approachable.

The brute force approach

The naive way is to first find the maximum depth, then collect all nodes at that depth, and finally find their lowest common ancestor.

def subtree_with_all_deepest_brute(root):
    def max_depth(node):
        if not node:
            return 0
        return 1 + max(max_depth(node.left), max_depth(node.right))

    def collect_deepest(node, depth, target):
        if not node:
            return []
        if depth == target:
            return [node]
        return collect_deepest(node.left, depth + 1, target) + collect_deepest(node.right, depth + 1, target)

    def lca(node, nodes):
        if not node or node in nodes:
            return node
        left = lca(node.left, nodes)
        right = lca(node.right, nodes)
        if left and right:
            return node
        return left or right

    target = max_depth(root)
    deepest = collect_deepest(root, 1, target)
    return lca(root, set(deepest))

This works but requires three separate traversals. You compute the max depth, collect the deepest nodes, then find their LCA. That is O(n) time for each pass, and the code is longer than it needs to be.

The key insight: if left depth equals right depth, current node is the answer

Here is the observation that simplifies everything. At any node, you can ask: "How deep does my left subtree go, and how deep does my right subtree go?"

There are three cases:

1. Left depth equals right depth. The deepest nodes exist in both subtrees. This node is the smallest subtree that contains all of them.
2. Left depth is greater. All the deepest nodes are in the left subtree. The answer is whatever the left subtree returned.
3. Right depth is greater. All the deepest nodes are in the right subtree. The answer is whatever the right subtree returned.

That is it. You recurse to the bottom, compute depths on the way back up, and the answer reveals itself at the node where left and right depths match.

Walking through it step by step

Let's trace through the tree [3,5,1,6,2,0,8,null,null,7,4]. At each node, we compare the depths returned by the left and right children.

The recursion bubbles up depth information from the leaves. At node 2, both children (7 and 4) return depth 1, so node 2 is the answer for that subtree. At node 5, the right side (depth 2 from node 2) is deeper than the left side (depth 1 from node 6), so it passes up node 2. At the root, the left side (depth 3) is deeper than the right side (depth 2), so it passes up node 2 again. The final answer is node 2.

The optimal solution

def subtree_with_all_deepest(root):
    def dfs(node):
        if not node:
            return None, 0
        left_node, left_depth = dfs(node.left)
        right_node, right_depth = dfs(node.right)
        if left_depth == right_depth:
            return node, left_depth + 1
        if left_depth > right_depth:
            return left_node, left_depth + 1
        return right_node, right_depth + 1

    return dfs(root)[0]

Let's break down each piece:

• if not node: return None, 0 is the base case. A null node has no subtree and depth 0.
• left_node, left_depth = dfs(node.left) recurses into the left subtree and gets back the candidate answer node along with its depth.
• right_node, right_depth = dfs(node.right) does the same for the right subtree.
• if left_depth == right_depth: return node, left_depth + 1 is the key line. Both sides go equally deep, so all deepest nodes span both subtrees, and the current node is their smallest common ancestor.
• if left_depth > right_depth: return left_node, left_depth + 1 means the deepest nodes are all on the left, so pass up the left answer.
• return right_node, right_depth + 1 handles the case where the right side is deeper.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node we do O(1) work (two comparisons and a return).

Space is O(n) in the worst case for the recursion stack. A completely skewed tree (essentially a linked list) would have a call stack n levels deep. For a balanced tree, space is O(log n).

Building blocks

1. Post-order aggregation (bottom-up recursion)

The decision at each node depends on results from both children. You recurse first, then combine. The skeleton looks like this:

def solve(node):
    if not node:
        return BASE_VALUE
    left = solve(node.left)
    right = solve(node.right)
    return AGGREGATE(node, left, right)

For this problem, the aggregation logic compares depths and picks the appropriate node. This same bottom-up structure drives solutions for maximum depth, balanced binary tree, and diameter of binary tree. The details of the aggregation change, but the recursive skeleton is identical.

2. Depth tracking with tuple returns

Instead of returning a single value, the recursive function returns a tuple of (node, depth). This lets the parent access two pieces of information from each child. The pattern generalizes: any time you need to make a decision that depends on more than one property of a subtree, bundle those properties into a tuple and return them together.

Edge cases

• Single node tree: The root is both the deepest node and the answer. dfs returns (root, 1).
• All leaves at the same depth (perfect binary tree): Every leaf is a deepest node. The LCA of all leaves is the root, so the root is returned.
• Skewed tree (linked list shape): Only one deepest node exists (the bottom of the chain). The function always follows the deeper side, returning that single leaf.
• Only one deepest node: The left and right depths never match except at the leaf itself. The leaf is returned as the answer.
• Two deepest nodes that are siblings: Their parent sees equal depths from both sides and returns itself. This is the most common case.
• Root is null: Returns None from the base case. The [0] indexing on the return value gives None.

Common mistakes

Forgetting to add 1 to the depth. When you return from a child, you need to increment the depth. Each level adds 1. If you forget, all depths stay at 0 and the root always looks like the answer.

Returning the node but not the depth. If your recursive function only returns a node, the parent has no way to compare left and right depths. You need both pieces of information. The tuple return is essential.

Trying to find deepest nodes first. Many people instinctively want to do a BFS to find the max depth, then find all nodes at that depth, then compute their LCA. This works but is unnecessarily complex. The single-pass approach handles everything at once.

Confusing this with LCA. This problem is related to lowest common ancestor, but it is not the same. In LCA you are given two specific target nodes. Here, the "targets" are all nodes at maximum depth, and you discover them during the recursion rather than knowing them upfront.

From understanding to recall

You just traced through a clean recursive solution that compares left and right depths at every node. You understand why equal depths mean "this node is the answer" and why unequal depths mean "pass up the deeper side." It makes sense right now.

But will you remember the three cases when you see this in an interview? Will you remember to return a tuple of (node, depth) instead of just a node? Will you remember that equal depths mean the current node is the answer, not a deeper node?

Understanding is not recall. You understood the logic. Recall means you can write the three-way comparison from memory, without hesitating over which case returns node versus left_node versus right_node.

Spaced repetition builds recall. You practice reconstructing the solution from scratch at increasing intervals. After a few repetitions, the post-order aggregation pattern and the depth comparison logic become automatic. You do not think about them. You just write them.

Related posts

• Lowest Common Ancestor - Uses the same post-order aggregation pattern but searches for two specific target nodes instead of comparing depths
• Diameter of Binary Tree - Another problem where left and right subtree depths drive the answer, using global max with local return instead of tuple returns
• Balanced Binary Tree - Compares left and right heights at every node, a similar depth comparison pattern with a different aggregation decision
• Maximum Depth of Binary Tree - The foundational depth recursion that this problem builds on top of