Problem Breakdown
Restatement: We are given a binary tree where each node has a depth defined as its distance from the root (0-indexed). Our goal is to identify all nodes that have the maximum possible depth in this specific instance of the tree. Once identified, we must return the smallest subtree rooted at some ancestor such that it contains all these deepest nodes and nothing else unnecessary.
Inputs:
root: The root node of a binary tree (TreeNode).
Outputs:
- A single
TreeNoderepresenting the root of the minimal valid subtree.
Implicit Constraints & Edge Cases:
- Tree Structure: Binary Tree (can be skewed or balanced).
- Node Values: Unique integers between 0 and 500.
- Empty Input: The constraints specify node count
[1, 500], so the tree is never empty (rootexists), but our code should handleNonegracefully for recursion base cases. - Deepest Nodes Definition: If multiple branches have leaves at the same maximum depth relative to the original root, they are all considered “deepest”. The answer must be their Lowest Common Ancestor (LCA).
Intuition
Brute Force Approach: A naive approach might involve:
- Calculating the max depth of every node using BFS/DFS ().
- Collecting all nodes at that max depth into a list.
- Iterating through each candidate subtree to see if it contains all collected deepest nodes, keeping track of the smallest one found so far.
Why Brute Force is Insufficient:
- Step 1 takes .
- Step 2 identifies candidates ( nodes).
- Step 3 requires checking containment for each candidate against all other deepest nodes. In a skewed tree, this could degrade to or worse depending on implementation complexity. It involves redundant traversals of the same subtrees multiple times.
Key Insight:
We can solve this in a single bottom-up pass using Depth-First Search (DFS). For any node u, we want to know two things:
- What is the height of the deepest leaf within its subtree?
- Which node represents the smallest valid answer for that specific branch?
Consider a node with left child depth and right child depth :
- If , it implies there are deepest nodes in both subtrees at this level (or deeper). The current node
uis the Lowest Common Ancestor of these deepest leaves. Since we want the smallest subtree, returninguhere is correct because any ancestor above would be a larger valid subtree containing unnecessary shallower nodes. - If , say , then all “deepest” nodes relevant to this branch are located in the left side (or deeper down). The right side contributes no deepest leaves relative to
u’s perspective compared to the left, so we discard the current node and return the result from the taller subtree.
Optimal Approach:
A recursive DFS that returns a tuple (height_of_subtree_rooted_here, candidate_node) for each call. We compare heights at every step to decide whether to promote the current node or pass up one of its children’s results.
Approach
- Define a helper function
dfs(node). - Base Case: If
nodeisNone, return(height = -1, candidate = None). Using-1simplifies height arithmetic (a leaf node will have left/right heights of -1). - Recursive Step: Call
dfs(left)anddfs(right). Let the results be(h_left, res_left)and(h_right, res_right). - Comparison Logic:
- If
h_left == h_right: The deepest nodes in this subtree are distributed across both children (or one child is empty). The current node becomes the root of our answer for this branch because it covers all deep leaves found so far at equal depth levels below. Return(max(h) + 1, self_node). - If
h_left > h_right: All deepest nodes are in the left subtree (or deeper down). The right side is irrelevant to finding the LCA of max-depth nodes here. Return(h_left + 1, res_left). - If
h_right > h_left: Symmetric case. Return(h_right + 1, res_right).
- If
- Final Result: Call
dfs(root)and return the second element of the returned tuple (the candidate node).
Complexity Analysis
- Time Complexity: , where is the number of nodes in the tree. We visit every node exactly once during the DFS traversal.
- Space Complexity: for recursion stack space, where is the height of the binary tree. In a balanced tree this is ; in a skewed (linked-list) tree it degrades to .
Solution
# 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
def subtreeWithAllDeepest(root: 'TreeNode') -> 'TreeNode':
# Helper function returning (height_of_subtree_rooted_here, candidate_node)
def dfs(node):
if not node:
return -1, None
h_left, res_left = dfs(node.left)
h_right, res_right = dfs(node.right)
# If depths are equal from both sides, current node is the LCA of deepest nodes.
# We want smallest subtree, so we stop going up if heights match (current level).
if h_left == h_right:
return max(h_left, h_right) + 1, node
# If one side is deeper, all deepest leaves are on that side.
# Propagate the result from the taller branch upwards.
else:
height = max(h_left, h_right) + 1
candidate = res_left if h_left > h_right else res_right
return height, candidate
_, ans_node = dfs(root)
return ans_node
Edge Cases Handled
- Single Node Tree:
dfsreturns-1, Nonefor children. Root’s left/right are -1/None. Heights match (-1 == -1). Returns root as answer. Correct. - Skewed Left Tree (e.g., 3 -> 5): Right child is empty (
h=-1). Left child has depthd. Sinced > -1, we propagate left result up the chain until reaching a point where heights match or end at root. The deepest node propagates all the way to its own branch’s LCA logic, which eventually resolves correctly as it climbs back up only when depths align (which they do for skewed trees effectively). - Multiple Deepest Nodes in Different Branches: If left and right subtrees both contain leaves of equal max depth relative to original root,
h_left == h_righttriggers at the current node. This identifies the correct LCA without traversing further up unnecessarily (which would create a larger subtree than required). - Null Root: Constraints guarantee
[1, 500], but logic handles null gracefully by returning None immediately if passed todfs.