Implementation in C++
//Program to remove subtrees containing zeroes in a binary tree
#include <bits/stdc++.h>
using namespace std;
//Class for the nodes of a tree.
class treenode {
public:
int value;
treenode* left;
treenode* right;
treenode(int num)
{
value = num;
left = nullptr;
right = nullptr;
}
};
//Function to print a binary tree.
void printbt(treenode* curr)
{
treenode* root=curr;
if (root == NULL)
{
return;
}
printbt(root->left);
cout << root->value << " ";
printbt(root->right);
}
//Function to remove subtrees containing zeroes in a binary tree
treenode* removesubt(treenode* root)
{
//Base case.
if (!root)
{
return NULL;
}
//Making recursive calls with left and right childrens of a node, when they are not null.
root->left=removesubt(root->left);
root->right=removesubt(root->right);
//When a node has its value equal to zero and both children equal to null.
if(root->value==0&&root->left==NULL&&root->right==NULL)
{
return NULL;
}
return root;
}
//Driver function.
int main()
{
//Creating the binary tree.
treenode* root = new treenode(12);
root->left = new treenode(11);
root->right = new treenode(0);
root->left->left = new treenode(9);
root->left->right = new treenode(0);
root->right->left = new treenode(0);
root->right->right = new treenode(0);
root->left->left->left = new treenode(5);
root->left->left->right = new treenode(0);
root->left->right->left = new treenode(3);
root->left->right->right = new treenode(0);
root->right->left->left = new treenode(1);
//Function calls
cout<<"Initial binary tree-"<<endl;
printbt(root);
cout<<endl;
removesubt(root);
cout<<"Modified binary tree-"<<endl;
printbt(root);
return 0;
}
You can also try this code with Online C++ Compiler
Output-
Initial binary tree-
5 9 0 11 3 0 0 12 1 0 0 0
Modified binary tree-
5 9 11 3 0 12 1 0 0
Complexity Analysis
Time complexity: The time complexity of this approach is -O(N), where N is the number of nodes in the binary tree.
Space complexity: The space complexity of this approach is - O(Height of the binary tree).
Check out this problem - Mirror A Binary Tree
Frequently Asked Questions
What is a node in a binary tree?
All the elements of a tree are known as nodes, and they contain the value of the elements, pointers to the child nodes. In the case of a binary tree, there could be at most two children.
What is a binary tree?
A binary tree is a data structure in programming languages to represent the hierarchy. Each node of the binary tree can have either 0,1, or 2 children.
What are leaves in a binary tree?
Leaves in a binary tree refer to nodes with no children, as both the pointers for the children nodes point to the null.
What is a subtree?
A portion of a group of a few nodes of a tree is called a subtree. The only condition is that the subtree's root must contain all of its children and their children.
What is a binary search tree?
A binary search tree is a sorted binary tree in which all the nodes of the binary tree have a value greater than their left child node and a value smaller than their right child node.
Conclusion
In this blog, we discussed how we could remove subtrees containing zeroes in a binary tree. We start with traversing the binary tree and for each node, checking if its value is zero and if both the children nodes are null. If both the conditions are true, we delete the node and its children, and if a node does not fulfill these conditions, we keep it in the binary tree. Once we are done traversing through each node, we print the modified binary tree.
Recommended Reading:
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Cheers!
84+ registered