Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution for the problem
2.1.
Algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a node in a binary tree?
4.2.
What is a binary tree?
4.3.
What are leaves in a binary tree?
4.4.
What is a subtree?
4.5.
What is a binary search tree?
5.
Conclusion
Last Updated: Mar 27, 2024

How to Remove Subtrees Containing Zeroes in a Binary Tree

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss the solution to the programming problem, in which we are given a binary tree, and we need to remove subtrees containing zeroes in a binary tree.

For example, consider the binary tree given below, the left child of the node with value three and the subtree with the right child of the node containing value 2, as its root is a subtree containing only zeroes thus we can remove them and we will be left with the tree on the right.

Also see, Data Structures

Binary Tree

 

Solution for the problem

Now, we need to devise a method that can remove subtrees containing zeroes in a binary tree. The basic idea to solve this problem is to traverse through the binary tree and remove nodes with both the left and right children as null and root equal to 0. So we start with traversing the tree in post-order and for every node, check if the node is null or not. If it's null, we return null. Else check for the left and right children of the node; if both are null and the node's value is zero, we return null or return the node as it is.

Algorithm

  • Create a binary tree or take it as user input.
  • Start traversing through the binary tree and check each node for the following -
  • If it is null, return null.
  • If it contains zero as the value in the node and both of its children are null, return null.
  • Else return the node as it is.
  • Print the modified binary tree.
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

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

 

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!

Previous article
Minimum Value to be Added at every Binary Tree Level to make the Sum at all Levels Equal
Next article
Change a Binary Tree so that every node stores sum of all nodes in left subtree
Live masterclass