1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ implementation
3.1.1.
Output
3.2.
Complexities
3.2.1.
Time complexity
3.2.2.
Space complexity
4.
4.1.
What is the depth of a node in a binary tree?
4.2.
What is a binary tree?
4.3.
What is a binary tree used for?
4.4.
What is a subtree of a tree?
4.5.
How to compare two subtrees?
5.
Conclusion
Last Updated: Mar 27, 2024

# Smallest Subtree with all the Deepest Nodes

Shreya Deep
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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(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

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.

### 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: