Smallest Subtree with all the Deepest Nodes — Solution
Smallest Subtree with all the Deepest Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Smallest Subtree with all the Deepest Nodes is a medium coding problem on hash table, depth-first search and breadth-first search, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Hash Table, Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree with distinct values, the deepest nodes are those at the greatest distance from the root.
Return the smallest subtree that contains all of the deepest nodes — that is, the subtree rooted at their lowest common ancestor. The subtree of a node is the node plus all of its descendants; return it as that subtree's level order.
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: The deepest nodes are 7 and 4; the smallest subtree holding both is the one rooted at their parent 2.
Example 2
Input: root = [1]
Output: [1]
Explanation: The root is the only, and so the deepest, node.
Example 3
Input: root = [0,1,3,null,2]
Output: [2]
Explanation: 2 is the single deepest node, and the smallest subtree containing it is 2 alone.
Constraints
The number of nodes in the tree is in the range [1, 500]0 <= Node.val <= 500The values of the nodes in the tree are unique
Hints for Smallest Subtree with all the Deepest Nodes
Hint 1
If the left subtree is deeper than the right one, every deepest node is on the left — the answer is inside the left subtree.
Hint 2
If both subtrees have the same depth, the deepest nodes are split between them (or the node is a leaf), so the node itself is the answer.
Hint 3
One post-order DFS can return two things per node: its subtree's depth and the answer for that subtree.
How to solve Smallest Subtree with all the Deepest Nodes
Compare the depths of the two subtrees at every node. The deeper side holds all the deepest nodes, so its answer carries up unchanged; when the depths tie, the deepest nodes lie on both sides and the current node is their lowest common ancestor.
Approach
deep(node)returns(depth, answer); for null it is(0, null).- Compute
(dl, l) = deep(left)and(dr, r) = deep(right). - If
dl > dr, return(dl + 1, l); ifdr > dl, return(dr + 1, r). - If they are equal, return
(dl + 1, node). The answer is the second part ofdeep(root).
Why it works
By induction, deep returns the height of a subtree and the lowest node containing all of that subtree's deepest nodes. If one side is strictly deeper, the subtree's deepest nodes all lie in it, so its answer is correct here too; if the sides tie, deepest nodes occur on both sides (or the node is a leaf), and the only node containing both groups is the node itself.
Complexity
- Time —
O(n) — each node is visited once - Space —
O(h) for the recursion
Pitfalls
- Computing heights separately at every node makes it O(n^2) on a chain; return depth and answer together.
- A single deepest node is its own answer — the subtree is just that node (with its descendants, of which it has none).
Reference solution
Python
from typing import Optional
def subtreeWithAllDeepest(root: Optional[TreeNode]) -> Optional[TreeNode]:
def deep(node):
if node is None:
return 0, None
dl, l = deep(node.left)
dr, r = deep(node.right)
if dl > dr:
return dl + 1, l
if dr > dl:
return dr + 1, r
return dl + 1, node
return deep(root)[1]Java
public static TreeNode subtreeWithAllDeepest(TreeNode root) {
return deepest(root, new int[1]);
}
// Returns the answer for the subtree and stores its depth in depth[0].
static TreeNode deepest(TreeNode node, int[] depth) {
if (node == null) { depth[0] = 0; return null; }
int[] a = new int[1], b = new int[1];
TreeNode l = deepest(node.left, a), r = deepest(node.right, b);
if (a[0] > b[0]) { depth[0] = a[0] + 1; return l; }
if (b[0] > a[0]) { depth[0] = b[0] + 1; return r; }
depth[0] = a[0] + 1;
return node;
}C++
pair<int, TreeNode*> deepest(TreeNode* node);
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
return deepest(root).second;
}
pair<int, TreeNode*> deepest(TreeNode* node) {
if (!node) return {0, nullptr};
auto a = deepest(node->left), b = deepest(node->right);
if (a.first > b.first) return {a.first + 1, a.second};
if (b.first > a.first) return {b.first + 1, b.second};
return {a.first + 1, node};
}JavaScript
var subtreeWithAllDeepest = function(root) {
return deepest(root)[1];
};
var deepest = function(node) {
if (node === null) return [0, null];
var a = deepest(node.left), b = deepest(node.right);
if (a[0] > b[0]) return [a[0] + 1, a[1]];
if (b[0] > a[0]) return [b[0] + 1, b[1]];
return [a[0] + 1, node];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)