How to remove subtrees containing zeroes in a binary tree

Gorakhnath yadav
Last Updated: May 13, 2022

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.

 

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.

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

Frequently asked questions

  1. 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.
  2. 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.
  3. 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.
  4. What is 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. 
  5. 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.

Key takeaways

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.

You can learn more about binary trees here. Also, don’t forget to practice similar problems on Code studio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think