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.
This approach leverages DFS to determine the depth of each node while recursively finding the subtree containing all the deepest nodes. By tracking depth, we can identify the lowest common ancestor of the deepest nodes, which will be the root of the smallest subtree containing them all.
The Python solution defines a DFS function that recursively traverses the tree, returning the lowest common ancestor and the maximum depth found. At each node, the function compares the maximum depths of its left and right children. If both have equal depth, the current node is part of the smallest subtree containing all deepest nodes.
Time Complexity: O(N), since all nodes must be visited.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.
This solution calculates the height of the tree nodes starting from the leaves (bottom-up). By evaluating the heights of left and right subtrees, the method determines the lowest common ancestor (LCA) of the deepest nodes, thereby identifying the desired subtree.
The Python solution defines a helper function `height` to recursively compute the height from each node and a function `lcaDeepestLeaves` to find the node acting as the common ancestor of the deepest leaves. Comparisons between left and right heights guide the decision toward the correct subtree.
Time Complexity: O(N^2) in the worst case due to repeated height calculations.
Space Complexity: O(H), corresponding to recursion use by `height` method.
We design a function dfs(root) that returns the smallest subtree containing all the deepest nodes in the subtree rooted at root, as well as the depth of the subtree rooted at root.
The execution process of the function dfs(root) is as follows:
root is null, return null and 0.root, denoted as l and l_d, and r and r_d, respectively. If l_d > r_d, then the smallest subtree containing all the deepest nodes in the subtree rooted at the left child of root is l, with a depth of l_d + 1. If l_d < r_d, then the smallest subtree containing all the deepest nodes in the subtree rooted at the right child of root is r, with a depth of r_d + 1. If l_d = r_d, then root is the smallest subtree containing all the deepest nodes, with a depth of l_d + 1.Finally, return the first element of the result of dfs(root).
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) with Depth Calculation | Time Complexity: O(N), since all nodes must be visited. |
| Bottom-Up Approach Using Tree Height and LCA | Time Complexity: O(N^2) in the worst case due to repeated height calculations. |
| Recursion | — |
| 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 |
Lowest Common Ancestor of Deepest Leaves | Smallest Subtree with all the Deepest Nodes | 1123 | 865 • codestorywithMIK • 18,289 views views
Watch 9 more video solutions →Practice Smallest Subtree with all the Deepest Nodes with our built-in code editor and test cases.
Practice on FleetCode