865. Smallest Subtree with all the Deepest Nodes LeetCode Solution
In this guide, you will get 865. Smallest Subtree with all the Deepest Nodes LeetCode Solution with the best time and space complexity. The solution to Smallest Subtree with all the Deepest Nodes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Smallest Subtree with all the Deepest Nodes
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.
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/
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
865. Smallest Subtree with all the Deepest Nodes LeetCode Solution in C++
struct T {
TreeNode* lca;
int depth;
};
class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
return dfs(root).lca;
}
private:
T dfs(TreeNode* root) {
if (root == nullptr)
return {nullptr, 0};
const T left = dfs(root->left);
const T right = dfs(root->right);
if (left.depth > right.depth)
return {left.lca, left.depth + 1};
if (left.depth < right.depth)
return {right.lca, right.depth + 1};
return {root, left.depth + 1};
}
}; /* code provided by PROGIEZ */
865. Smallest Subtree with all the Deepest Nodes LeetCode Solution in Java
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
return dfs(root).lca;
}
private record T(TreeNode lca, int depth) {}
private T dfs(TreeNode root) {
if (root == null)
return new T(null, 0);
T left = dfs(root.left);
T right = dfs(root.right);
if (left.depth > right.depth)
return new T(left.lca, left.depth + 1);
if (left.depth < right.depth)
return new T(right.lca, right.depth + 1);
return new T(root, left.depth + 1);
}
} // code provided by PROGIEZ
865. Smallest Subtree with all the Deepest Nodes LeetCode Solution in Python
