Leetcode 865. Smallest Subtree with all the Deepest Nodes
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?
Brute Force Code
/**
* 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<TreeNode> queue = new LinkedList<>();
Set<TreeNode> 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<TreeNode> 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)
Queue<TreeNode> queue = new LinkedList<>();
Set<TreeNode> deepestNodes = new HashSet<>();
int i = 0; // Current level
int max = 0; // Maximum level seen so farNote: 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)
int getDeepestNodes(TreeNode root, Set<TreeNode> deepNodes)Time & Space Complexity
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
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:
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 2Comparison
| 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:
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.