Smallest Subtree with all the Deepest Nodes

Problem Statement

Given the root of a binary tree, where the depth of each node is determined as the shortest distance from the root, the task is to identify the smallest possible subtree that encompasses all the deepest nodes in the entire tree. The concept of "deepest nodes" refers to those nodes that are located at the maximum depth achievable within the tree. A subtree, with respect to a node, includes that node itself along with all its descendants.

Examples

Example 1

Input:

root = [3,5,1,6,2,0,8,null,null,7,4]

Output:

[2,7,4]

Explanation:

We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

Example 2

Input:

root = [1]

Output:

[1]

Explanation:

The root is the deepest node in the tree.

Example 3

Input:

root = [0,1,3,null,2]

Output:

[2]

Explanation:

The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

Constraints

• The number of nodes in the tree will be in the range [1, 500].
• 0 <= Node.val <= 500
• The values of the nodes in the tree are unique.

Approach and Intuition

To solve the problem of finding the smallest subtree containing all the deepest nodes, one can employ a bottom-up traversal strategy (post-order traversal). The core intuition behind this approach is rooted in two observations:

1. The depth of each node needs to be computed to identify the deepest nodes.
2. A shared ancestor node that is closest to these deepest nodes can encase the required smallest subtree.

Here are the structured steps to implement the solution:

1. Initiate a helper function that operates in a post-order traversal manner, which calculates the depth of its subtree while checking for deepest nodes.
   • If the node is null, return the current depth as 0.
   • Recursively retrieve the depth of left and right subtrees.
   • If the left and right subtrees’ maximum depths are equal, it indicates that the current node is the common ancestor to all deepest nodes found in its subtrees.
   • If one subtree is deeper than the other, propagate the deeper subtree's root node upward as a potential answer.
   • Return the maximum depth encountered via the current node to its parent node.
2. The root of the tree is passed to this helper function.
3. Depending on the largest depths encountered in the left and right subtrees of each node, either the node itself becomes the smallest subtree if both subtree depths are equal, or the deeper subtree's node does.

This approach ensures the return of the smallest subtree covering all deepest nodes by continuously narrowing down the potential ancestor nodes based on subtree depths. Since each node's subtree depth is calculated while simultaneously checking for potential common ancestors, the process remains efficient. Moreover, this solution adjusts dynamically to the configuration of the tree, seamlessly handling wide, narrow, balanced, or skewed trees.

Solutions

class Solution {
    public TreeNode findDeepestSubtree(TreeNode root) {
        return explore(root).node;
    }

    public Result explore(TreeNode node) {
        if (node == null) return new Result(null, 0);
        Result leftResult = explore(node.left),
               rightResult = explore(node.right);
        if (leftResult.dist > rightResult.dist) return new Result(leftResult.node, leftResult.dist + 1);
        if (leftResult.dist < rightResult.dist) return new Result(rightResult.node, rightResult.dist + 1);
        return new Result(node, leftResult.dist + 1);
    }
}

class Result {
    TreeNode node;
    int dist;
    Result(TreeNode n, int d) {
        node = n;
        dist = d;
    }
}