Smallest subtree with all the deepest nodes

Shreya Deep
Last Updated: May 13, 2022

Introduction

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. The end nodes which don’t have any children are called leaf nodes. The depth of a node is the distance between the node and the root of the 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. 

In this article, we will see how to find the smallest subtree, which contains all the deepest nodes.

Problem Statement

Given a binary tree, find the smallest subtree that contains all the deepest nodes of the tree and return the root of this smallest subtree.

For example:

Output: 7

Explanation: In this example, 1 is the root, so 8 and 9 are the deepest nodes. And the subtree containing both these nodes is the one whose root is 7. Thus, the output is 7.

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

O(n2), 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(n2).

Space complexity

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

  1. 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.
     
  2. 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.
     
  3. 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.
     
  4. 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.
     
  5. How to compare two subtrees?
    A subtree A is said to be smaller than a subtree B if the number of nodes in A is less than the number of nodes in B.

Key Takeaways

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. 

You can look for more problems based on the binary tree. Some of these are the largest number in a binary treetriplets in a binary treemaximum depth of a binary treeLCA of a binary treeminimum depth in a binary tree, and height of the binary tree

These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and overview student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think