Domain 2MediumMEDIUM

Smallest Subtree with all the Deepest Nodes

LeetCode problem 865: Smallest Subtree with all the Deepest Nodes (medium).

Domain: medium•Updated: 2026-09-02
#Tree#Depth-first Search#Breadth-first Search#Recursion

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 TreeNode representing the root of the minimal valid subtree.

Implicit Constraints & Edge Cases:

  1. Tree Structure: Binary Tree (can be skewed or balanced).
  2. Node Values: Unique integers between 0 and 500.
  3. Empty Input: The constraints specify node count [1, 500], so the tree is never empty (root exists), but our code should handle None gracefully for recursion base cases.
  4. 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:

  1. Calculating the max depth of every node using BFS/DFS (O(N)O(N)).
  2. Collecting all nodes at that max depth into a list.
  3. 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 O(N)O(N).
  • Step 2 identifies candidates (KK nodes).
  • Step 3 requires checking containment for each candidate against all other deepest nodes. In a skewed tree, this could degrade to O(K⋅N)O(K \cdot N) 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:

  1. What is the height of the deepest leaf within its subtree?
  2. Which node represents the smallest valid answer for that specific branch?

Consider a node with left child depth hLh_L and right child depth hRh_R:

  • If hL==hRh_L == h_R, it implies there are deepest nodes in both subtrees at this level (or deeper). The current node u is the Lowest Common Ancestor of these deepest leaves. Since we want the smallest subtree, returning u here is correct because any ancestor above would be a larger valid subtree containing unnecessary shallower nodes.
  • If hL≠hRh_L \neq h_R, say hL>hRh_L > h_R, 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

  1. Define a helper function dfs(node).
  2. Base Case: If node is None, return (height = -1, candidate = None). Using -1 simplifies height arithmetic (a leaf node will have left/right heights of -1).
  3. Recursive Step: Call dfs(left) and dfs(right). Let the results be (h_left, res_left) and (h_right, res_right).
  4. 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).
  5. Final Result: Call dfs(root) and return the second element of the returned tuple (the candidate node).

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the number of nodes in the tree. We visit every node exactly once during the DFS traversal.
  • Space Complexity: O(H)O(H) for recursion stack space, where HH is the height of the binary tree. In a balanced tree this is O(log⁡N)O(\log N); in a skewed (linked-list) tree it degrades to O(N)O(N).

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: dfs returns -1, None for 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 depth d. Since d > -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_right triggers 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 to dfs.