Smallest Subtree with all the Deepest Nodes

• Pass 1: Find Maximum Depth
  1. Initialize a global variable, maxDepth, to -1.
  2. Create a recursive DFS function, findMaxDepth(node, depth), that traverses the tree.
  3. In this function, if the node is null, return. Otherwise, update maxDepth = Math.max(maxDepth, depth).
  4. Recursively call for the left and right children with depth + 1.
  5. Start the traversal by calling findMaxDepth(root, 0).
• Pass 2: Find the Smallest Subtree (LCA)
  1. Create another recursive function, findLCA(node, depth), that returns a TreeNode.
  2. This function performs a post-order traversal. If the current node is null, it returns null.
  3. If the current depth equals the maxDepth found in Pass 1, this node is one of the deepest nodes, so return it.
  4. Recursively call findLCA for the left and right children: leftLCA = findLCA(node.left, depth + 1) and rightLCA = findLCA(node.right, depth + 1).
  5. If both leftLCA and rightLCA are non-null, it means deepest nodes exist in both subtrees. The current node is their lowest common ancestor, so return node.
  6. If only one of them is non-null, it means all deepest nodes in this subtree are in that one branch. Propagate the result up by returning the non-null LCA.
  7. If both are null, it means no deepest nodes are in this subtree, so return null.
  8. The final answer is the result of findLCA(root, 0).

The first pass is a standard Depth-First Search (DFS) to determine the maximum depth of any node in the tree. We use a helper function that takes a node and its current depth as arguments, and we maintain a global variable maxDepth that is updated whenever a greater depth is found.

After the first pass completes, maxDepth holds the depth of the deepest nodes. The second pass also uses a recursive DFS function. This function's goal is to find the LCA of all nodes at maxDepth. It works by checking the results from its left and right subtrees. If deepest nodes are found in both subtrees (indicated by non-null return values from both recursive calls), the current node is the LCA. If a node itself is at maxDepth, it is considered an LCA for its own subtree. If deepest nodes are only in one subtree, the result from that subtree is passed up the recursion chain. The node returned by the second pass for the root of the tree is the final answer.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private int maxDepth = -1;18 19    public TreeNode subtreeWithAllDeepest(TreeNode root) {20        // Pass 1: Find the maximum depth of the tree21        findMaxDepth(root, 0);22        // Pass 2: Find the LCA of all nodes at maxDepth23        return findLCA(root, 0);24    }25 26    private void findMaxDepth(TreeNode node, int depth) {27        if (node == null) {28            return;29        }30        maxDepth = Math.max(maxDepth, depth);31        findMaxDepth(node.left, depth + 1);32        findMaxDepth(node.right, depth + 1);33    }34 35    private TreeNode findLCA(TreeNode node, int depth) {36        if (node == null) {37            return null;38        }39 40        // If this node is at the max depth, it's a deepest node.41        if (depth == maxDepth) {42            return node;43        }44 45        // Recursively search in left and right subtrees.46        TreeNode leftLCA = findLCA(node.left, depth + 1);47        TreeNode rightLCA = findLCA(node.right, depth + 1);48 49        // If both subtrees contain deepest nodes, the current node is the LCA.50        if (leftLCA != null && rightLCA != null) {51            return node;52        }53 54        // Otherwise, the LCA must be in the subtree that contains deepest nodes.55        return leftLCA != null ? leftLCA : rightLCA;56    }57}

1. Define a helper class, Result, to store a pair of values: a TreeNode and an int for depth.
2. Create a recursive DFS function, dfs(node), that returns a Result object.
3. Base Case: If node is null, return a Result with a null node and a depth of -1. This serves as the starting point for depth calculation.
4. Recursive Step: Perform a post-order traversal. Make recursive calls for the left and right children: leftResult = dfs(node.left) and rightResult = dfs(node.right).
5. Combine Results:
   • Compare the depths from the left and right results.
   • If leftResult.depth > rightResult.depth, the deepest nodes are in the left subtree. Return a new Result containing the LCA from the left (leftResult.node) and an updated depth (leftResult.depth + 1).
   • If rightResult.depth > leftResult.depth, the deepest nodes are in the right subtree. Return a new Result with the LCA from the right (rightResult.node) and updated depth (rightResult.depth + 1).
   • If leftResult.depth == rightResult.depth, the deepest nodes are in both subtrees (or the current node is a leaf). This means the current node is the new LCA. Return a Result containing the current node and the updated depth (leftResult.depth + 1).
6. The final answer is the node part of the Result returned by the initial call dfs(root).

This method uses a single recursive function, let's call it dfs, which performs a post-order traversal. For any node, dfs is called on its children first. The function returns a pair of values: (node, depth), where node is the LCA of the deepest leaves in the subtree, and depth is the depth of those leaves relative to the subtree's root.

When combining results at a parent node, we compare the depths returned from the left and right children.

• If one child's subtree has a greater depth, it means all the deepest nodes are in that subtree, so we pass its LCA and updated depth upwards.
• If the depths are equal, it means the deepest nodes are spread across both subtrees. In this case, the current node becomes the new LCA.

This process continues up to the root of the tree, and the final LCA returned for the root is the answer to the problem.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    // Helper class to bundle the result: the node and its depth.18    private class Result {19        TreeNode node;20        int depth;21 22        Result(TreeNode node, int depth) {23            this.node = node;24            this.depth = depth;25        }26    }27 28    public TreeNode subtreeWithAllDeepest(TreeNode root) {29        return dfs(root).node;30    }31 32    private Result dfs(TreeNode node) {33        // Base case: an empty subtree has a depth of -1.34        if (node == null) {35            return new Result(null, -1);36        }37 38        // Post-order traversal: process children first.39        Result leftResult = dfs(node.left);40        Result rightResult = dfs(node.right);41 42        // The depth of the current node's result is 1 + the depth of its children's result.43        int currentDepth = 1 + Math.max(leftResult.depth, rightResult.depth);44 45        // Compare depths from left and right subtrees.46        if (leftResult.depth > rightResult.depth) {47            // Deepest nodes are in the left subtree.48            return new Result(leftResult.node, currentDepth);49        } else if (rightResult.depth > leftResult.depth) {50            // Deepest nodes are in the right subtree.51            return new Result(rightResult.node, currentDepth);52        } else {53            // Depths are equal, so the current node is the LCA.54            return new Result(node, currentDepth);55        }56    }57}