Watch 10 video solutions for Smallest Subtree with all the Deepest Nodes, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by codestorywithMIK has 18,289 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Explanation: We return the node with value 2, colored in yellow in the diagram. The nodes coloured in blue are the deepest nodes of the tree. Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
Example 2:
Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree.
Example 3:
Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.
Constraints:
[1, 500].0 <= Node.val <= 500
Note: This question is the same as 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
Problem Overview: You are given the root of a binary tree. The goal is to return the smallest subtree that contains all the deepest nodes in the tree. If multiple deepest nodes exist, the answer is the lowest common ancestor (LCA) of those nodes along with its entire subtree.
Approach 1: Depth First Search (DFS) with Depth Calculation (O(n) time, O(h) space)
This method performs a Depth-First Search to compute the depth of nodes while recursively exploring the tree. For each node, recursively compute the deepest depth of its left and right subtrees. If both sides have the same maximum depth, the current node becomes the root of the smallest subtree containing all deepest nodes. If one side is deeper, propagate that subtree upward. The recursion effectively returns both the candidate node and its depth, allowing the algorithm to determine the correct subtree root in a single traversal.
Approach 2: Bottom-Up Approach Using Tree Height and LCA (O(n) time, O(h) space)
This approach treats the problem as a Lowest Common Ancestor computation among the deepest nodes. First determine subtree heights using a recursive traversal of the Binary Tree. While unwinding the recursion, compare the height of the left and right subtrees. If both heights match, the current node is the LCA of the deepest nodes. If one side is taller, continue propagating the deeper subtree upward. Because each node is processed once, the algorithm runs in linear time and uses recursion stack space proportional to the tree height.
Both strategies rely on properties of tree traversal and recursion. The key insight is that the smallest subtree containing all deepest nodes must be the lowest node where the maximum depth appears in both left and right branches.
Recommended for interviews: The bottom-up DFS approach that returns both depth and subtree root is the most common interview solution. It solves the problem in a single traversal with O(n) time and clean recursion logic. Showing the reasoning around subtree depth comparison demonstrates strong understanding of tree recursion and LCA concepts.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Depth Calculation | O(n) | O(h) | General case; clean recursive solution that determines subtree root during traversal |
| Bottom-Up Height + LCA Approach | O(n) | O(h) | Preferred interview method; combines height calculation and LCA detection in one DFS |