Smallest Subtree with all the Deepest Nodes

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

7

You can also try this code with Online C++ Compiler

Run Code

Complexities

Time complexity

The time complexity is O(n²), 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²).

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:

• Largest number in a binary tree
• Triplets in a binary tree
• Maximum depth of a binary tree
• LCA of a binary tree
• Aggressive Cows
• Minimum depth in a binary tree
• Height of the binary tree
• Deepest Left

Recommended Reading:

• Queue
• Check if All the Nodes in the Binary Tree are having Common Values that are at least D Distance Apart
• Print Cousins of Given Node of Binary Tree
• Check if Given Binary Tree is a Sum Tree

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!