Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Optimized Approach 
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are the different members of a TreeNode class?
4.2.
What do you understand by tree traversals? Explain PostOrder Traversal?
4.3.
What are the uses of Inorder, Preorder, and Postorder Traversals?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if removing an edge can Divide a Binary Tree into Two halves.

Author Sarthak
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Nowadays, problems based on Binary Tree are a Hot topic for many companies and are frequently asked in Goldman Sachs, Microsoft, and Amazon. So, do you want to become a ninja and get into these giant companies?

Today this article will discuss one of those problems based on Binary Tree.

Problem Statement

We were given a Binary Tree with N nodes. Check if removing an edge can divide the Binary Tree into two halves.

Sample Example

Input:

We are given a given a Binary Tree of size n. A particular node can have maximum of two children.You 
are given root node of the binary tree.

 

Output:  

This Binary Tree can be splitted Into Two Parts Of Equal Size.

In the given figure, If we cut the left root edge, the Tree is divided into two parts of equal size. The left part of the Tree has a size of 5, and the right part of the Tree also has five nodes.

Brute Force Approach

The Approach is very simple. It is a Recursive. First, we calculate the total number of nodes in the Binary Tree. If the Total number of nodes in the Binary Tree is odd, then return false. Now, We will traverse the entire Tree, and For every Node, find the number of nodes in the subtree. If the number of nodes in the subtree is half the total Node, then return true.

Implementation in C++

#include <iostream>
using namespace std;
// Structure and Creation Of New Node
struct Node
{
    int data;
    Node *left;
    Node *right;

    Node(int val)
    {
        data = val;
        left = right = NULL;
    }
};

// Function To find total Number of Node in Binary Tree
int TotalNumberOfNode(Node *root)
{
    if (root == NULL)
        return 0;
    int NodesInLeftSubtree = TotalNumberOfNode(root->left);
    int NodesInRightSubtree = TotalNumberOfNode(root->right);
    int total = NodesInLeftSubtree + NodesInRightSubtree + 1;
    return total;
}

bool IsSplitingingTree(Node *root, int n)
{
    // Base cases
    if (root == NULL)
        return false;
    // Calculating number of nodes for every subtree in given  tree
    int x = TotalNumberOfNode(root);

    // If number of nodes in a particular subtree is half of total number of tree
    if (x == n / 2)
        return true;

    // Checking If Left Subtree has any dividing Edge
    bool LeftSubtree = IsSplitingingTree(root->left, n);

    // Checking If Left Subtree has any dividing Edge
    bool RightSubtree = IsSplitingingTree(root->right, n);

    // Taking Union (means whole tree has traversed)
    bool ans = LeftSubtree || RightSubtree;
    return ans;
}
int main()
{
    // Creation Of Tree
    struct Node *root = new Node(8);
    root->left = new Node(4);
    root->right = new Node(7);

    root->left->left = new Node(3);
    root->left->right = new Node(6);

    root->right->left = new Node(1);
    root->right->right = new Node(2);

    root->left->left->left = new Node(0);
    root->left->left->right = new Node(5);

    root->right->left->left = new Node(9);

    // Counting  Total Number Of nodes in given tree
    int n = TotalNumberOfNode(root);
    if (n % 2 != 0)
    {
        cout << "This Binary Tree cannot  be splitted Into Two Parts Of Equal Size" << endl;
        return 0;
    }
    // Recursive function to check whether the tree is dividing between anywhere.
    bool splitfunction = IsSplitingingTree(root, n);
    if (splitfunction == 1)
    {
        cout << "This Binary Tree can be splitted Into Two Parts Of Equal Size" << endl;
    }
    else
    {
        cout << "This Binary Tree cannot  be splitted Into Two Parts Of Equal Size" << endl;
    }
    return 0;
}

 

Output:

This Binary Tree can be splitted Into Two Parts Of Equal Size

 

Complexity Analysis

Time complexity: O(n²), where n is the number of nodes in a tree.

As there are n nodes in a binary tree and we are using a loop for every node,Hence, our time complexity is O(n²).

Space complexity: O(n).

We are using Recursion and it makes a stack of size n.Hence Space complexity is O(n).

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

Optimized Approach 

This approach is quite similar to the post-order traversal of a Binary Tree. We will traverse Tree bottom up, so we don't have to find the size of the subtree of nodes again and again like the brute force approach.

We will start from the bottom of the Tree. Then we calculate the size of the left subtree and right subtree and return it to the parents. The total number of nodes of a particular tree is one more than the addition of the left and right subtree. Hence, we have calculated the number of nodes of any subtree in the whole Tree.

Implementation in C++

#include <iostream>
using namespace std;
// Structure and Creation Of New Node
struct Node
{
    int data;
    Node *left;
    Node *right;

    Node(int val)
    {
        data = val;
        left = right = NULL;
    }
};

// Function To find total Number of Node in Binary Tree
int TotalNumberOfNode(Node *root)
{
    if (root == NULL)
        return 0;

    // Nodes in Left Subtree
    int NodesInLeftSubtree = TotalNumberOfNode(root->left);

    // Nodes in Left Subtree
    int NodesInRightSubtree = TotalNumberOfNode(root->right);

    // Total number of nodes in a subtree
    int total = NodesInLeftSubtree + NodesInRightSubtree + 1;
    return total;
}

int IsSplitingingTree(Node *root, int n, bool &result)
{
    // Base case
    if (root == NULL)
        return 0;

    // Calculate sizes of left and right subtree
    int NodesInLeftSubtree = IsSplitingingTree(root->left, n, result);
    int NodesInRighttSubtree = IsSplitingingTree(root->right, n, result);

    // size of particular subtree
    int z = NodesInLeftSubtree + NodesInRighttSubtree + 1;

    // If number of nodes in a particular subtree is half of total number of tree
    if (z == n / 2)
        result = true;
    return z;
}
int main()
{
    // Creation Of Tree
    struct Node *root = new Node(8);
    root->left = new Node(4);
    root->right = new Node(7);

    root->left->left = new Node(3);
    root->left->right = new Node(6);

    root->right->left = new Node(1);
    root->right->right = new Node(2);

    root->left->left->left = new Node(0);
    root->left->left->right = new Node(5);

    root->right->left->left = new Node(9);

    // Counting  Total Number Of nodes in given tree
    int n = TotalNumberOfNode(root);

    // If There are Odd Number of Nodes in the tree,return false
    if (n % 2 != 0)
    {
        cout << "This Binary Tree cannot  be splitted Into Two Parts Of Equal Size" << endl;
        return 0;
    }
    // Initialisation of a variable 'result'.
    bool result = false;

    // Recursive function to check whether the tree is dividing between anywhere.
    bool splitfunction = IsSplitingingTree(root, n, result);

    if (splitfunction == 1)
    {
        cout << "This Binary Tree can be splitted Into Two Parts Of Equal Size" << endl;
    }
    else
    {
        cout << "This Binary Tree cannot  be splitted Into Two Parts Of Equal Size" << endl;
    }
    return 0;
}

 

Output:

This Binary Tree can be splitted Into Two Parts Of Equal Size

 

Complexity Analysis

Time complexity: O(n), we don't have to traverse again to find the size of the left subtree and right subtree. Therefore the complexity is O(n)

Space complexity: O(n), Algorithm uses recursion. Therefore it takes a stack.

Frequently Asked Questions

What are the different members of a TreeNode class?

There are three types of members in the Tree class node:-

  • Data.
  • Pointer to Left child.
  • Pointer to Right child.

What do you understand by tree traversals? Explain PostOrder Traversal?

It refers to the process of visiting each node in a tree data structure exactly once. How you visit each node determines the name of traversal.

In PostOrder traversal, we traverse the left subtree, then the right subtree, and then visit the node.

What are the uses of Inorder, Preorder, and Postorder Traversals?

Uses of Inorder,PreOrder,and Postorder traversal :-

Inorder Traversal: If we need to find sorted order in the Binary search tree, we can find it using Inorder traversal, as Inorder traversal gives the sorted order of the binary search tree.

Preorder Traversal: Pre-order traversal can be used to get the prefix expression of an expression tree. It is used to create a copy of the Tree. 

Postorder Traversal: Post Order Traversal is used to delete the Tree. It is also used to get the postfix expression of an expression tree.

Conclusion

In this blog, we discussed how to Check If removing an edge can divide a binary Tree, discussed the various approaches to solving this problem, also saw its time and space complexity, and learned how to optimize the Approach by reducing the time complexity of the problem. We hope you will learn something from this and will continue learning.

Suggested problems are Construct a Binary Tree From Preorder and PostorderConstruct a Binary Tree From its Linked-List Representation, and many more.

Check out Uber Interview Experience to learn about their hiring process.

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingDBMSSystem DesignWeb Development, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! However, if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problemsinterview experiences, and interview bundle.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

 

Happy Learning!

Previous article
Specific Level Order Traversal of Binary Tree
Next article
Postorder Traversal of Binary tree
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass