C++ program to check if removing an edge can divide a Binary Tree into two halves

By Pratyush Gupta

In this tutorial, we will learn how to check if removing an edge can divide a Binary Tree into two halves. Rather than just getting directly to the solution lets us discuss the basic idea and also on how to approach the question step by step. We will try to understand the process in-depth to make us familiar with this type of question.

First of all, we have to notice that to divide a binary tree into two halves it must have even number of total nodes. So If the number of nodes is odd it is not possible.

The naive approach is to remove all edges one by one and count the number of vertices in both the parts. And if they are equal then possible.

Let’s analyze the time complexity :

If V=number of vertices then Total edges E=V-1. If you planning to apply DFS to count the number of vertices then

Time Complexity = Number of Edges *( DFS for part 1 +DFS for part 2); In general time DFS time complexity is O(2*V-1);

Here Worst-case Time complexity is=(V-1)*(V-1) =appox V*V. So this approach is not feasible in competitive programming.

Therefore Lets us discuss the more efficient approach: Time Complexity O(V). If somehow we know the count of vertices in both parts prior then the job is done. Lets us get a more clear view with the help of this example.

Look at the above the tree :

Number of vertices in the tree with root as 11 N(11) =1 ;

Number of vertices in the tree with root as 12 N(12) = N(11)+1 ;

with root as N(5) =N(10) + N(12) +1 ;

with root as N(2) =N(5) + N(1) + 1;

Here comes the most important part, the role of observation skills. Are you getting the pattern? Yes, you guessed it right.

Number of vertices associated with a vertex is  N(Vertex) = N(left_child) + N(right_child) + 1 (for itself) . If you are familiar with the bottom-down approach of memorization then this is cake piece for you. We can easily do this with the help of recursive functions.

Basic Idea: What we have to do

In other words, we need to find a node (vertex) such that:

the number of nodes in the right_subtree is equal to the number of nodes in the left_subtree+1 OR

the number of nodes in the left_subtree is equal to the number of nodes in the right_subtree+1.

In conclusion, in simple words, we are searching for a node such that the number of vertices its subtree including itself if equal to half of the total number of vertices in the given tree.

Algorithm:

1. Count the total number of nodes in the given tree through get_Count_Of_Nodes() function.
2. Make use of the CheckIfDivide Function to calculate the number of nodes of left_subtree and right_tree of the node and then check the condition of this is equal to half total nodes of the tree. If yes then increment the (global variable) ways.

Go through the implementation which is self-explanatory.

class TreeNode
{
  public:
  int val;

  //this pointer will point left child 
  struct TreeNode *leftChild;

  //this pointer will point right child
  struct TreeNode *rightChild;
};

TreeNode *Node(int data)
{   
     TreeNode *node=new TreeNode;
     //initialising the data to the struct variable val
     //"val" personal int data storage variable of every node 
     node->val=data;
     //initialsing the left and right pointer as NULL 
     node->leftChild=node->leftChild=NULL;

     return node;
}

get_Count_Of_Node() function

int get_Count_Of_Nodes(TreeNode *root)
{
       if(root==NULL)
       {
        return 0;
       }
       //If the leaf node is acting as root node then return 1
       //beacuse the count of all nodes i  s 1 ( leaf node itself)
 
       if(root->leftChild==NULL&&root->rightChild==NULL)
       return 1;

      //To count the number of nodes in the left subtree  
      int left_count_of_nodes=get_Count_Of_Nodes(root->leftChild);

      //To count the number of nodes in the right subtree
      int right_count_of_nodes=get_Count_Of_Nodes
      (root->rightChild);

      //Initialing total=1 to count the root node itself
      int total=1;
      //total = rootnode +nodes in left subtree + nodes 
      //in right subtree
      total+=left_count_of_nodes+right_count_of_nodes;
      return total;
    
}

Input  : Root pointer
Output : Returns 8 as the total number of nodes in the tree.

CheckIfDivide() function

Recursive_Function_To_check_If_Tree_Can_be_divied_in_to_halve

int CheckIfDivide(TreeNode *root,int totalNodes)
{

      if(root==NULL)
      {
        return 0 ;
      }
      
      //To count the number of nodes in the left subtree  
      int left_count_of_nodes=CheckIfDivide
      (root->leftChild,totalNodes);

      //To count the number of nodes in the right subtree
      int right_count_of_nodes=CheckIfDivide
      (root->rightChild,totalNodes);

      //Initialing total=1 to count the root node itself
      int total=1;

      //total = rootnode +nodes in left subtree + nodes 
      //in right subtree
      total+=left_count_of_nodes+right_count_of_nodes;
      
      //check the condition if the the total is equal to
      //half of the totalNodes
      if(total==totalNodes/2)
      {
        ways++;
      }
      return total;

}

void solve(TreeNode *root)
{

   int totalNodes=get_Count_Of_Nodes(root);

   cout<<"Total number of nodes present in the given tree is ";
   cout<<totalNodes<<endl;

   //Condition to check if number of nodes in even b/c if
   //then only it is possible ot divides

   if(totalNodes%2==0)
   {
   //Function_To_check_If_Tree_Can_be_divied_in_to_halves
   CheckIfDivide(root,totalNodes);
 
   }

 
   if(ways>0)
   {
     cout<<"YES"<<'\n';
   }

   else 
   {
     cout<<"NO"<<'\n';
   }

}

Root Pointer

The total number of nodes present in the given tree is 8.
YES for the tree being discussed here.

Tree  Used to demonstrate the code :

int main()
{
    
    //Decalring the root node ;
    TreeNode *root;

    root=Node(2);

    root->leftChild=Node(1);

    root->rightChild=Node(5);


    root->leftChild->leftChild=Node(4);

    root->leftChild->rightChild=Node(9);

    root->rightChild->leftChild=Node(10);

    root->rightChild->rightChild=Node(12);

    root->rightChild->rightChild->rightChild=Node(10);

    //Diver function()
    solve(root);

    return 0;
}