Skip to main content
Talentd

Smallest Subtree with all the Deepest Nodes - Solution & Explanation

MediumHash TableTreeDepth-First SearchBreadth-First Search22 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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:

  • The number of nodes in the tree will be in the range [1, 500].
  • 0 <= Node.val <= 500
  • The values of the nodes in the tree are unique.

 

Note: This question is the same as 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

Approach Overview

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 1: Depth First Search (DFS) with Depth Calculation

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Bottom-Up Approach Using Tree Height and LCA

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Recursion

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:

  • If root is null, return null and 0.
  • Otherwise, recursively calculate the smallest subtree and depth of the left and right subtrees of 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth First Search (DFS) with Depth Calculation

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.

Bottom-Up Approach Using Tree Height and LCA

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.

Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Depth CalculationO(n)O(h)General case; clean recursive solution that determines subtree root during traversal
Bottom-Up Height + LCA ApproachO(n)O(h)Preferred interview method; combines height calculation and LCA detection in one DFS

Video Solution

Lowest Common Ancestor of Deepest Leaves | Smallest Subtree with all the Deepest Nodes | 1123 | 865 • codestorywithMIK • 19,362 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Subtree with all the Deepest Nodes easy or hard?
Smallest Subtree with all the Deepest Nodes is considered a Medium difficulty problem. The challenge comes from recognizing that the answer is the lowest common ancestor of the deepest nodes and implementing that logic efficiently with DFS.
Smallest Subtree with all the Deepest Nodes Python/Java solution
Python, Java, and C++ implementations usually use recursive DFS. Each function call returns the deepest depth and the node representing the smallest subtree. The logic remains the same across languages with only syntax differences.
How to solve Smallest Subtree with all the Deepest Nodes in O(n)?
Perform a DFS that returns a pair: the depth of the deepest node in the subtree and the subtree root containing those nodes. If left and right depths are equal, return the current node. If one side is deeper, propagate that subtree upward. Since every node is processed once, the total runtime is O(n).
What is the best approach for Smallest Subtree with all the Deepest Nodes?
The best approach is a bottom-up Depth First Search that returns both subtree depth and the candidate node. During recursion, compare the depths of the left and right subtrees. If both depths are equal, the current node becomes the smallest subtree containing all deepest nodes. This solution runs in O(n) time and uses O(h) recursion stack space.
Is Smallest Subtree with all the Deepest Nodes asked at Google/Amazon/Meta?
Tree recursion and Lowest Common Ancestor style problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of DFS traversal, subtree depth calculations, and LCA concepts in binary trees.
What data structure is used in Smallest Subtree with all the Deepest Nodes?
The problem uses a binary tree as the primary data structure. The solution typically applies Depth First Search recursion and Lowest Common Ancestor logic to determine the subtree containing all deepest nodes.
What is the time complexity of Smallest Subtree with all the Deepest Nodes?
The optimal solution runs in O(n) time where n is the number of nodes in the binary tree. Each node is visited exactly once during the DFS traversal. The space complexity is O(h), where h is the height of the tree due to the recursion stack.

Ready to solve this problem?

Practice Smallest Subtree with all the Deepest Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters