Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node:
                return (0, None)
            left_depth, left_node = dfs(node.left)
            right_depth, right_node = dfs(node.right)
            if left_depth > right_depth:
                return (left_depth + 1, left_node)
            elif right_depth > left_depth:
                return (right_depth + 1, right_node)
            else:
                return (left_depth + 1, node)
        return dfs(root)[1]
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    pair dfs(TreeNode* node) {
        if (!node) return {0, nullptr};
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        if (left.first > right.first)
            return {left.first + 1, left.second};
        else if (right.first > left.first)
            return {right.first + 1, right.second};
        else
            return {left.first + 1, node};
    }
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
};
      

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private class Result {
        int depth;
        TreeNode node;
        Result(int d, TreeNode n) {
            depth = d;
            node = n;
        }
    }

    private Result dfs(TreeNode node) {
        if (node == null) return new Result(0, null);
        Result left = dfs(node.left);
        Result right = dfs(node.right);
        if (left.depth > right.depth)
            return new Result(left.depth + 1, left.node);
        else if (right.depth > left.depth)
            return new Result(right.depth + 1, right.node);
        else
            return new Result(left.depth + 1, node);
    }

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var subtreeWithAllDeepest = function(root) {
    function dfs(node) {
        if (!node) return [0, null];
        const [leftDepth, leftNode] = dfs(node.left);
        const [rightDepth, rightNode] = dfs(node.right);
        if (leftDepth > rightDepth) {
            return [leftDepth + 1, leftNode];
        } else if (rightDepth > leftDepth) {
            return [rightDepth + 1, rightNode];
        } else {
            return [leftDepth + 1, node];
        }
    }
    return dfs(root)[1];
};
      

Problem Description

Given the root of a binary tree, you are asked to find the smallest subtree that contains all the deepest nodes in the tree. The "deepest nodes" are defined as the nodes that are the farthest from the root (i.e., have the greatest depth).

The output should be the root node of this smallest subtree. If there are multiple deepest nodes, the subtree should be the lowest common ancestor (LCA) of all these nodes. It is guaranteed that there is exactly one such subtree.

• Each node has a unique value.
• The tree is non-empty.
• You should not reuse elements or create new nodes, just return the existing node in the tree.

Thought Process

At first glance, the problem seems to require identifying all the deepest nodes in the binary tree and then finding their lowest common ancestor (LCA). A brute-force approach would be to:

• Traverse the tree to find the maximum depth.
• Collect all nodes at this depth.
• Compute the LCA for all these nodes.

However, this approach may be inefficient, especially if the tree is large. Instead, we can optimize by combining the depth calculation and ancestor finding into a single post-order traversal. The key insight is that for each node, if its left and right subtrees have the same maximum depth, then this node is the LCA of the deepest nodes in its subtree.

By thinking recursively, we can return both the depth and the candidate subtree root from each recursive call, so that each parent can make the right decision without extra passes or storage.

Solution Approach

We use a post-order DFS (Depth-First Search) traversal to solve the problem efficiently in one pass. Here’s how:

1. Define a helper function that, for each node, returns two things:
   • The maximum depth from this node down to a leaf.
   • The subtree root that contains all the deepest nodes in this subtree.
2. Base Case: If the node is null, return depth 0 and subtree null.
3. Recursive Case:
   • Recursively call the helper on the left and right children.
   • If the left and right depths are equal, then this node is the LCA of the deepest nodes.
   • If one side is deeper, propagate up the deeper subtree's root and increase the depth.
4. Return: At the end, the helper returns the subtree root that contains all the deepest nodes.

This method is efficient because it avoids redundant traversals and directly computes the answer in a single DFS.

Example Walkthrough

Consider the following binary tree:

        3
       / \
      5   1
     /|   |\
    6 2   0 8
      /\
     7  4
  

Step-by-step:

1. The deepest nodes are 7 and 4, both at depth 4.
2. The smallest subtree containing both is rooted at node 2.
3. During DFS:
   • At node 7 and 4, return (depth=1, node=self).
   • At node 2, left and right depths are equal (both 1), so return (2, node 2).
   • At node 5, left depth (1) < right depth (2), so propagate (3, node 2) up.
   • At root, compare left (3, node 2) and right (2, node 1), left is deeper, so propagate (4, node 2).
4. The answer is node 2.

Time and Space Complexity

• Brute-force Approach:
  • Time: O(N^2) if you compute LCA for all pairs of deepest nodes separately.
  • Space: O(N) for storing nodes and recursion stack.
• Optimized DFS Approach (this solution):
  • Time: O(N), where N is the number of nodes, since each node is visited once.
  • Space: O(H), where H is the height of the tree, due to recursion stack (O(log N) for balanced, O(N) for skewed trees).

Summary

The problem asks us to find the smallest subtree containing all the deepest nodes of a binary tree. By using a post-order DFS that returns both depth and candidate subtree, we combine the tasks of finding the deepest nodes and their lowest common ancestor into a single traversal. This approach is elegant, efficient, and leverages the recursive nature of trees to avoid redundant work.