Smallest Subtree with all the Deepest Nodes

Given the root of a binary tree, the depth of each node is the shortest distance to the root. Return the smallest subtree such that it contains all the deepest nodes in the original tree. A node is called the deepest if it has the largest depth possible among any node in the entire tree. The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Approach 1: Paint Deepest Nodes

class Solution {
    Map depth;
    int max_depth;
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        depth = new HashMap();
        depth.put(null, -1);
        dfs(root, null);
        max_depth = -1;
        for (Integer d: depth.values())
            max_depth = Math.max(max_depth, d);

        return answer(root);
    }

    public void dfs(TreeNode node, TreeNode parent) {
        if (node != null) {
            depth.put(node, depth.get(parent) + 1);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }

    public TreeNode answer(TreeNode node) {
        if (node == null || depth.get(node) == max_depth)
            return node;
        TreeNode L = answer(node.left),
                    R = answer(node.right);
        if (L != null && R != null) return node;
        if (L != null) return L;
        if (R != null) return R;
        return null;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

Smallest Subtree with all the Deepest Nodes

The problem Smallest Subtree with all the Deepest Nodes is a fascinating challenge in binary tree analysis. It involves determining the smallest subtree that contains all the deepest nodes in a binary tree. This problem is an excellent test of tree traversal techniques and depth calculation logic.

Problem Statement

Given the root of a binary tree, return the root of the smallest subtree that contains all the deepest nodes. A node is considered "deepest" if it is at the maximum depth of the binary tree.

Key points:

• There may be multiple deepest nodes.
• The smallest subtree is the subtree rooted at the lowest common ancestor of all the deepest nodes.

Approach to Solve the Problem

Solving this problem involves two main steps:

1. Calculate Depths

Perform a depth-first search (DFS) to determine the maximum depth of the tree and identify the deepest nodes.

2. Identify the Smallest Subtree

Use a recursive approach to find the lowest common ancestor (LCA) of all the deepest nodes. This LCA will be the root of the smallest subtree containing all the deepest nodes.

Implementation

Here is the Python implementation:

class Solution:
    def subtreeWithAllDeepest(self, root):
        def dfs(node):
            if not node:
                return (0, None)
            left_depth, left_subtree = dfs(node.left)
            right_depth, right_subtree = dfs(node.right)

            if left_depth > right_depth:
                return (left_depth + 1, left_subtree)
            elif right_depth > left_depth:
                return (right_depth + 1, right_subtree)
            else:
                return (left_depth + 1, node)

        return dfs(root)[1]
        

Here is a Java implementation:

class Solution {
    class Result {
        TreeNode node;
        int depth;
        Result(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
    
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }

    private Result dfs(TreeNode node) {
        if (node == null) return new Result(null, 0);

        Result left = dfs(node.left);
        Result right = dfs(node.right);

        if (left.depth > right.depth) {
            return new Result(left.node, left.depth + 1);
        } else if (right.depth > left.depth) {
            return new Result(right.node, right.depth + 1);
        } else {
            return new Result(node, left.depth + 1);
        }
    }
}
        

Example

Consider the binary tree:

            Tree Structure:
                3
               / \
              5   1
             / \ / \
            6  2 0  8
               / \
              7   4
        

In this tree:

• The deepest nodes are 7 and 4.
• The smallest subtree containing both is the subtree rooted at 2.

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once during the DFS traversal.

Space Complexity: O(h), where h is the height of the tree. This accounts for the recursive call stack.

Applications

• Identifying critical nodes in hierarchical data structures.
• Optimizing search operations in tree-based systems.
• Useful in graph-related problems where depth plays a key role.

Conclusion

The problem Smallest Subtree with all the Deepest Nodes is a classic tree problem that tests your understanding of depth calculation, recursion, and binary tree traversal. By carefully identifying the depths of nodes and recursively determining the lowest common ancestor, the problem can be solved efficiently.

Practice with variations of the problem to strengthen your grasp on recursion and tree manipulation techniques.