Solution Approach
Since we need to find the subtree that contains all the deepest nodes, for each node, we will keep going to the deeper side, i.e., if the left side is deeper than the right, we will go to the left, or if the right side is deeper than the left side, we will go to the right side, and if the depth of both the sides are same, it means weâ€™re on the root of the subtree that actually contains all the deepest node because both the sides are on equal depth so they both must be containing the deepest nodes and this node is the root of the tree that contains those nodes.
Steps are:

Construct a binary tree.

Call the function â€śfuncâ€ť which returns the root of the smallest subtree containing the deepest nodes.

In the function â€śfuncâ€ť:

First, write the base condition. If the root is null, return NULL.

Find the height of the left and the right subtrees. If the height of the left subtree exceeds that of the right subtree, it means the left subtree is deeper; go to the left subtree. If the height of the right subtree exceeds that of the left subtree, it means the right subtree is deeper; go to the right subtree. Otherwise, return the current node.

For finding the height of a node, we write another function, â€śheight.â€ť

In the function â€śheightâ€ť:
 If the root is NULL, return 0.
 If the root is a leaf node, return 1.

Otherwise, find the height of the left and the right subtree of the current root and then height = max(height of left subtree, height of right subtree)+1.
 Print the data of the node returned by the above Function.
C++ implementation
#include<bits/stdc++.h>
using namespace std;
template <typename T>
class BinaryTreeNode
{
// Class for BinaryTreeNode
public:
T data; // Data of the node
BinaryTreeNode* left; // Left of the node
BinaryTreeNode* right; // Right of the node
BinaryTreeNode(T data)
{ // Constructor for assigning the data to the current node
this>data=data;
left=NULL;
right=NULL;
}
};
// Function for finding the height of a node
int height(BinaryTreeNode<int>* root){
// If root is null, height = 0;
if (root==NULL)
return 0;
// if the root is the leaf node, height = 1;
if (root>left == NULL && root>right == NULL)
return 1;
// Otherwise, height = max(height of left subtree, height of right subtree)+1
return max(height(root>left),height(root>right)) + 1;
}
// Function for returning the root of the smallest subtree containing the
// deepest nodes
BinaryTreeNode<int>* func(BinaryTreeNode<int>* root)
{
// If root is null, return null
if (root==NULL)
return NULL;
// find the height of left subtree
int left_height = height(root>left);
// find the height of right subtree
int right_height = height(root>right);
// If height of left subtree exceeds that of the right subtree,
// go to the left subtree
if (left_height > right_height) {
// Traverse left subtree
func(root>left);
}
// If height of right subtree exceeds that of the left subtree,
// go to the right subtree
else if (right_height > left_height) {
func(root>right);
}
// Otherwise, return current node
else {
return root;
}
}
int main()
{
// Construct a Binary Tree
BinaryTreeNode<int> *root = NULL;
root = new BinaryTreeNode<int>(1);
root>left = new BinaryTreeNode<int>(2);
root>right = new BinaryTreeNode<int>(3);
root>left>left = new BinaryTreeNode<int>(4);
root>left>right = new BinaryTreeNode<int>(5);
root>right>left = new BinaryTreeNode<int>(7);
root>right>right = new BinaryTreeNode<int>(6);
root>right>left>left = new BinaryTreeNode<int>(8);
root>right>left>right = new BinaryTreeNode<int>(9);
// Call the function which returns the root of the smallest subtree
// containing the deepest nodes
BinaryTreeNode<int>*ans = func(root);
cout<<ans>data<<endl;
}
Output
7
Complexities
Time complexity
The time complexity is O(n^{2}), where n is the number of nodes.
Reason: Weâ€™re traversing the tree each time, either in the left or right direction. In the case when the given binary tree is skewed, this takes O(n) time. Finding the depths of the subtrees takes O(n) time in the worst case. Thus, the overall complexity is O(n^{2}).
Space complexity
The Space Complexity is O(1)
Reason: Weâ€™re only taking up spaces by creating variables, and this takes constant space. If we consider the recursion stack space then the space complexity will be O(h) where h=height of the binary tree.
Frequently Asked Questions
What is the depth of a node in a binary tree?
The depth of a node is defined as the length of the path from the root of the tree to the node.
What is a binary tree?
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
What is a binary tree used for?
In computing, binary trees are mainly used for searching and sorting as they provide a means to store data hierarchically.
What is a subtree of a tree?
A subtree of a tree, T is a tree, X whose root is a node of the tree T with all its descendants in T.
How to compare two subtrees?
A subtree A is said to be smaller than subtree B if the number of nodes in A is less than the number of nodes in B.
Conclusion
In this article, weâ€™ve discussed the problem of finding the smallest subtree with all the deepest nodes in a binary tree. This problem required a good understanding of the binary tree data structure.
Recommended Problems:
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Happy Coding!