Smallest Subtree with all the Deepest Nodes solution and explanation
Google
9 more videos on this problem
Lowest Common Ancestor of Deepest Leaves | Smallest Subtree with all the Deepest Nodes | 1123 | 865codestorywithMIK · 42:25 · 19K views
Smallest Subtree with all the Deepest Nodes | Live Coding with Explanation | Leetcode #865Algorithms Made Easy · 4:50 · 5K views
Smallest Subtree with all the Deepest Nodes | LeetCode 865 | Binary Tree DFS Study Placement · 24:22 · 2K views
Smallest Subtree with all the Deepest Nodes | LeetCode 865 | 3 ApproachesSanyam IIT Guwahati · 25:37 · 1K views
LeetCode 865. Smallest Subtree with all the Deepest NodesHappy Coding · 11:37 · 1K views
865. Smallest Subtree with all the Deepest Nodes | Leetcode Daily - PythonLeetcode Daily · 8:04 · 1K views
Daily Leetcode #2110: Jan 09, 2026 - 865. Smallest Subtree with all the Deepest NodesProgramming Live with Larry · 6:44 · 519 views
865. Smallest Subtree with all the Deepest Nodes - English VersionSimple Code - 단순코드 · 6:03 · 414 views
LeetCode 865. [Medium] Smallest Subtree with all the Deepest NodesFrancesco Manicardi · 7:36 · 380 views
Smallest Subtree with all the Deepest Nodes - Leetcode 865 - PythonTim Huang · 5:15 · 319 views
The problem
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
def dfs(node):
if not node: return (None, 0)
lca_left, depth_left = dfs(node.left)
lca_right, depth_right = dfs(node.right)
if depth_left > depth_right:
return (lca_left, depth_left + 1)
elif depth_right > depth_left:
return (lca_right, depth_right + 1)
else:
return (node, depth_left + 1)
return dfs(root)[0]class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
return dfs(root).node;
}
private Result dfs(TreeNode node) {
if (node == null) return new Result(null, 0);
Result left = dfs(node.left);
Result right = dfs(node.right);
if (left.depth > right.depth) return new Result(left.node, left.depth + 1);
if (right.depth > left.depth) return new Result(right.node, right.depth + 1);
return new Result(node, left.depth + 1);
}
private class Result {
TreeNode node;
int depth;
Result(TreeNode n, int d) {
node = n;
depth = d;
}
}
}#include <utility>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
return dfs(root).first;
}
std::pair<TreeNode*, int> dfs(TreeNode* node) {
if (!node) return {nullptr, 0};
auto left = dfs(node->left);
auto right = dfs(node->right);
if (left.second > right.second) return {left.first, left.second + 1};
if (right.second > left.second) return {right.first, right.second + 1};
return {node, left.second + 1};
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var subtreeWithAllDeepest = function(root) {
const dfs = (node) => {
if (!node) return {node: null, depth: 0};
const left = dfs(node.left);
const right = dfs(node.right);
if (left.depth > right.depth) return {node: left.node, depth: left.depth + 1};
if (right.depth > left.depth) return {node: right.node, depth: right.depth + 1};
return {node: node, depth: left.depth + 1};
};
return dfs(root).node;
};#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct Result {
struct TreeNode *node;
int depth;
};
struct Result dfs(struct TreeNode *node) {
if (!node) return (struct Result){NULL, 0};
struct Result left = dfs(node->left);
struct Result right = dfs(node->right);
if (left.depth > right.depth) return (struct Result){left.node, left.depth + 1};
if (right.depth > left.depth) return (struct Result){right.node, right.depth + 1};
return (struct Result){node, left.depth + 1};
}
struct TreeNode* subtreeWithAllDeepest(struct TreeNode* root) {
return dfs(root).node;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode SubtreeWithAllDeepest(TreeNode root) {
return DFS(root).node;
}
private (TreeNode node, int depth) DFS(TreeNode node) {
if (node == null) return (null, 0);
var left = DFS(node.left);
var right = DFS(node.right);
if (left.depth > right.depth) return (left.node, left.depth + 1);
if (right.depth > left.depth) return (right.node, right.depth + 1);
return (node, left.depth + 1);
}
}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.
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
def height(node):
if not node:
return 0
return max(height(node.left), height(node.right)) + 1
def lcaDeepestLeaves(node):
if not node:
return None
left_height = height(node.left)
right_height = height(node.right)
if left_height == right_height:
return node
elif left_height > right_height:
return lcaDeepestLeaves(node.left)
else:
return lcaDeepestLeaves(node.right)
return lcaDeepestLeaves(root)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int height(TreeNode node) {
if (node == null) return 0;
return Math.max(height(node.left), height(node.right)) + 1;
}
public TreeNode subtreeWithAllDeepest(TreeNode root) {
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == rightHeight) return root;
else if (leftHeight > rightHeight) return subtreeWithAllDeepest(root.left);
else return subtreeWithAllDeepest(root.right);
}
}#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int height(TreeNode* node) {
if (!node) return 0;
return std::max(height(node->left), height(node->right)) + 1;
}
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight == rightHeight) return root;
else if (leftHeight > rightHeight) return subtreeWithAllDeepest(root->left);
else return subtreeWithAllDeepest(root->right);
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var subtreeWithAllDeepest = function(root) {
const height = (node) => {
if (!node) return 0;
return Math.max(height(node.left), height(node.right)) + 1;
};
let leftHeight = height(root.left);
let rightHeight = height(root.right);
if (leftHeight == rightHeight) return root;
else if (leftHeight > rightHeight) return subtreeWithAllDeepest(root.left);
else return subtreeWithAllDeepest(root.right);
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int height(struct TreeNode *node) {
if (!node) return 0;
int left = height(node->left);
int right = height(node->right);
return left > right ? left + 1 : right + 1;
}
struct TreeNode* subtreeWithAllDeepest(struct TreeNode* root) {
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight == rightHeight) return root;
else if (leftHeight > rightHeight) return subtreeWithAllDeepest(root->left);
else return subtreeWithAllDeepest(root->right);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int Height(TreeNode node) {
if (node == null) return 0;
return Math.Max(Height(node.left), Height(node.right)) + 1;
}
public TreeNode SubtreeWithAllDeepest(TreeNode root) {
int leftHeight = Height(root.left);
int rightHeight = Height(root.right);
if (leftHeight == rightHeight) return root;
else if (leftHeight > rightHeight) return SubtreeWithAllDeepest(root.left);
else return SubtreeWithAllDeepest(root.right);
}
}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.
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
rootis null, returnnulland0. - Otherwise, recursively calculate the smallest subtree and depth of the left and right subtrees of
root, denoted aslandl_d, andrandr_d, respectively. Ifl_d > r_d, then the smallest subtree containing all the deepest nodes in the subtree rooted at the left child ofrootisl, with a depth ofl_d + 1. Ifl_d < r_d, then the smallest subtree containing all the deepest nodes in the subtree rooted at the right child ofrootisr, with a depth ofr_d + 1. Ifl_d = r_d, thenrootis the smallest subtree containing all the deepest nodes, with a depth ofl_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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function subtreeWithAllDeepest(root: TreeNode | null): TreeNode | null {
const dfs = (root: TreeNode | null): [TreeNode, number] => {
if (!root) {
return [null, 0];
}
const [l, ld] = dfs(root.left);
const [r, rd] = dfs(root.right);
if (ld > rd) {
return [l, ld + 1];
}
if (ld < rd) {
return [r, rd + 1];
}
return [root, ld + 1];
};
return dfs(root)[0];
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
type pair struct {
node *TreeNode
depth int
}
var dfs func(*TreeNode) pair
dfs = func(root *TreeNode) pair {
if root == nil {
return pair{nil, 0}
}
l, r := dfs(root.Left), dfs(root.Right)
ld, rd := l.depth, r.depth
if ld > rd {
return pair{l.node, ld + 1}
}
if ld < rd {
return pair{r.node, rd + 1}
}
return pair{root, ld + 1}
}
return dfs(root).node
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn subtree_with_all_deepest(
root: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
fn dfs(
root: Option<Rc<RefCell<TreeNode>>>,
) -> (Option<Rc<RefCell<TreeNode>>>, i32) {
if let Some(node) = root {
let left = node.borrow().left.clone();
let right = node.borrow().right.clone();
let (l, ld) = dfs(left);
let (r, rd) = dfs(right);
if ld > rd {
(l, ld + 1)
} else if ld < rd {
(r, rd + 1)
} else {
(Some(node), ld + 1)
}
} else {
(None, 0)
}
}
dfs(root).0
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.