# Problem Description 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. ## Example ``` Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Explanation: The deepest nodes are 7 and 4. Their lowest common ancestor is 2. ``` # Brute Force Solution Approach ## Thought Process This approach uses a **two-phase strategy**: 1. **Phase 1 - Find Deepest Nodes (BFS)**: Use level-order traversal to identify all nodes at the maximum depth 2. **Phase 2 - Find LCA (DFS)**: Use post-order traversal to find the Lowest Common Ancestor (LCA) of all deepest nodes ### Why This Approach? - **BFS for finding depth**: Level-order traversal naturally gives you nodes level by level, making it easy to identify the deepest level - **DFS for finding LCA**: Post-order traversal allows you to count how many deepest nodes are in each subtree, and the node where the count equals the total number of deepest nodes is the LCA ## Brute Force Code ```java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { TreeNode ans = null; boolean found = false; public TreeNode subtreeWithAllDeepest(TreeNode root) { Queue queue = new LinkedList<>(); Set deepestNodes = new HashSet<>(); queue.add(root); int i = 0; int max = 0; while(!queue.isEmpty()) { int len = queue.size(); while(len > 0){ TreeNode cur = queue.poll(); if(i == max){ deepestNodes.add(cur); }else if(i > max){ max = i; deepestNodes = new HashSet<>(); deepestNodes.add(cur); } len--; if(cur.left != null){ queue.offer(cur.left); } if(cur.right != null){ queue.offer(cur.right); } } i++; } getDeepestNodes(root,deepestNodes); return ans; } int getDeepestNodes(TreeNode root, Set deepNodes){ if(root == null){ return 0; } int leftCount = getDeepestNodes(root.left,deepNodes); if(deepNodes.contains(root)){ leftCount++; } int rightCount = getDeepestNodes(root.right,deepNodes); if(leftCount + rightCount == deepNodes.size() && !found){ ans = root; found = true; } return leftCount + rightCount; } } ``` ## Explanation of Brute Force Approach ### Phase 1: Finding Deepest Nodes (BFS) ```java Queue queue = new LinkedList<>(); Set deepestNodes = new HashSet<>(); int i = 0; // Current level int max = 0; // Maximum level seen so far ``` - The algorithm traverses the tree level by level using BFS - Tracks the current level with `i` - When a level deeper than `max` is found, the set is cleared and nodes at this new deepest level are collected - At the end, `deepestNodes` contains all nodes at the maximum depth **Note**: The variable `max` tracks the deepest level found during traversal. When `i > max`, it means a deeper level has been discovered. ### Phase 2: Finding LCA (DFS) ```java int getDeepestNodes(TreeNode root, Set deepNodes) ``` - This function counts how many deepest nodes are in the subtree rooted at `root` - **Post-order traversal**: First process left, then right, then current node - If the current node is a deepest node, the count is incremented - When `leftCount + rightCount == deepNodes.size()`, the LCA has been found - this is the first (lowest) node whose subtree contains all deepest nodes - The `found` flag ensures `ans` is only set once (the first time the LCA is found) ## Time & Space Complexity - **Time Complexity**: O(n) - BFS takes O(n), DFS takes O(n) - **Space Complexity**: O(n) - Queue for BFS, Set for deepest nodes, recursion stack for DFS ## Potential Issues & Improvements 1. **Variable naming**: `getDeepestNodes` returns a count, not nodes - consider renaming to `countDeepestNodes` 2. **The counting logic**: When the current node is a deepest node, `leftCount` is incremented, but conceptually it might be clearer to count it separately 3. **The `found` flag**: While it works, the algorithm could be optimized by returning early once the LCA is found # Optimal Solution (Single Pass) ## Approach Instead of two passes, we can do this in **one DFS pass** by: 1. For each node, return both its depth and the LCA of deepest nodes in its subtree 2. If both subtrees have the same max depth, the current node is the LCA 3. If one subtree is deeper, return that subtree's LCA ## Optimal Code ```java class Solution { public TreeNode subtreeWithAllDeepest(TreeNode root) { return dfs(root).node; } // Return both the depth and the LCA node private Result dfs(TreeNode root) { if (root == null) { return new Result(0, null); } Result left = dfs(root.left); Result right = dfs(root.right); // If both subtrees have same max depth, current node is LCA if (left.depth == right.depth) { return new Result(left.depth + 1, root); } // If one subtree is deeper, return that subtree's result if (left.depth > right.depth) { return new Result(left.depth + 1, left.node); } else { return new Result(right.depth + 1, right.node); } } class Result { int depth; TreeNode node; Result(int depth, TreeNode node) { this.depth = depth; this.node = node; } } } ``` ## Explanation of Optimal Approach ### Key Insight The LCA of all deepest nodes is the node where: - Both left and right subtrees contain deepest nodes at the **same depth** - OR one subtree is deeper (in which case the LCA is in that subtree) ### How It Works 1. **Base case**: Null node has depth 0 and no LCA 2. **Recursive case**: - Get depth and LCA from left and right subtrees - If depths are equal: Current node is the LCA (deepest nodes are in both subtrees) - If one is deeper: The LCA is in the deeper subtree 3. **Return**: Depth + 1 (for current level) and the appropriate LCA node ### Example Walkthrough ``` Tree: 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 DFS traversal: - Node 7: depth=0, LCA=7 - Node 4: depth=0, LCA=4 - Node 2: left depth=1, right depth=1 → LCA=2 (both subtrees have deepest nodes) - Node 6: depth=0, LCA=6 - Node 5: left depth=1, right depth=2 → LCA=2 (right subtree is deeper) - Node 0: depth=0, LCA=0 - Node 8: depth=0, LCA=8 - Node 1: left depth=1, right depth=1 → LCA=1 - Node 3: left depth=3, right depth=2 → LCA=2 (left subtree is deeper) Final answer: Node 2 ``` ## Comparison | Approach | Time | Space | Passes | |-----------------------|------|-------|-------------------| | Brute Force Solution | O(n) | O(n) | 2 (BFS + DFS) | | Optimal Solution | O(n) | O(h) | 1 (DFS only) | Both are O(n) time, but the optimal solution: - Uses less space (O(h) vs O(n) for the queue/set) - Only requires one pass - More elegant and easier to understand # Summary The brute force solution correctly solves the problem using a clear two-phase approach: 1. **BFS** to find all deepest nodes 2. **DFS** to find their LCA The optimal solution combines both steps into a single DFS pass by tracking depth and LCA together, making it more space-efficient and elegant.

Problems

Leetcode 865. Smallest Subtree with all the Deepest Nodes