Check if removing an edge can divide a Binary Tree in two halves

Last Updated : 30 Jun, 2022

Given a Binary Tree, find if there exists an edge whose removal creates two trees of equal size.

Examples:

Input : root of following tree
           5
         /   \
       1      6    
      /      /  \
     3      7    4
Output : true
Removing edge 5-6 creates two trees of equal size


Input : root of following tree
           5
         /   \
       1      6    
            /  \
           7    4
         /  \    \
        3    2    8
Output : false
There is no edge whose removal creates two trees
of equal size.

Source- Kshitij IIT KGP

Method 1 (Simple): First count number of nodes in whole tree. Let count of all nodes be n. Now traverse tree and for every node, find size of subtree rooted with this node. Let the subtree size be s. If n-s is equal to s, then return true, else false.

C++

// C++ program to check if there exist an edge whose
// removal creates two trees of same size
#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    int data;
    struct Node* left, *right;
};
 
// utility function to create a new node
struct Node* newNode(int x)
{
    struct Node* temp = new Node;
    temp->data = x;
    temp->left = temp->right = NULL;
    return temp;
};
 
// To calculate size of tree with given root
int count(Node* root)
{
    if (root==NULL)
        return 0;
    return count(root->left) + count(root->right) + 1;
}
 
// This function returns true if there is an edge
// whose removal can divide the tree in two halves
// n is size of tree
bool checkRec(Node* root, int n)
{
    // Base cases
    if (root ==NULL)
       return false;
 
    // Check for root
    if (count(root) == n-count(root))
        return true;
 
    // Check for rest of the nodes
    return checkRec(root->left, n) ||
           checkRec(root->right, n);
}
 
// This function mainly uses checkRec()
bool check(Node *root)
{
    // Count total nodes in given tree
    int n = count(root);
 
    // Now recursively check all nodes
    return checkRec(root, n);
}
 
// Driver code
int main()
{
    struct Node* root = newNode(5);
    root->left = newNode(1);
    root->right = newNode(6);
    root->left->left = newNode(3);
    root->right->left = newNode(7);
    root->right->right = newNode(4);
 
    check(root)?  printf("YES") : printf("NO");
 
    return 0;
}

Java

// Java program to check if there exist an edge whose
// removal creates two trees of same size
 
class Node 
{
    int key;
    Node left, right;
 
    public Node(int key) 
    {
        this.key = key;
        left = right = null;
    }
}
 
class BinaryTree 
{
    Node root;
 
    // To calculate size of tree with given root
    int count(Node node) 
    {
        if (node == null)
            return 0;
         
        return count(node.left) + count(node.right) + 1;
    }
 
    // This function returns true if there is an edge
    // whose removal can divide the tree in two halves
    // n is size of tree
    boolean checkRec(Node node, int n) 
    {
        // Base cases
        if (node == null) 
            return false;
 
        // Check for root
        if (count(node) == n - count(node))
            return true;
 
        // Check for rest of the nodes
        return checkRec(node.left, n)
                || checkRec(node.right, n);
    }
 
    // This function mainly uses checkRec()
    boolean check(Node node) 
    {
        // Count total nodes in given tree
        int n = count(node);
 
        // Now recursively check all nodes
        return checkRec(node, n);
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(1);
        tree.root.right = new Node(6);
        tree.root.left.left = new Node(3);
        tree.root.right.left = new Node(7);
        tree.root.right.right = new Node(4);
        if(tree.check(tree.root)==true)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
 
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python3 program to check if there 
# exist an edge whose removal creates
# two trees of same size 
 
# utility function to create a new node 
class newNode:
    def __init__(self, x):
        self.data = x 
        self.left = self.right = None
 
# To calculate size of tree 
# with given root 
def count(root):
    if (root == None):
        return 0
    return (count(root.left) +
            count(root.right) + 1)
 
# This function returns true if there 
# is an edge whose removal can divide 
# the tree in two halves n is size of tree 
def checkRec(root, n):
     
    # Base cases 
    if (root == None): 
        return False
 
    # Check for root 
    if (count(root) == n - count(root)):
        return True
 
    # Check for rest of the nodes 
    return (checkRec(root.left, n) or
            checkRec(root.right, n))
 
# This function mainly uses checkRec() 
def check(root):
     
    # Count total nodes in given tree 
    n = count(root) 
 
    # Now recursively check all nodes 
    return checkRec(root, n)
 
# Driver code 
if __name__ == '__main__':
    root = newNode(5) 
    root.left = newNode(1) 
    root.right = newNode(6) 
    root.left.left = newNode(3) 
    root.right.left = newNode(7) 
    root.right.right = newNode(4) 
 
    if check(root):
        print("YES")
    else: 
        print("NO")
         
# This code is contributed by PranchalK

C#

// C# program to check if there exist 
// an edge whose removal creates two 
// trees of same size 
using System;
 
public class Node
{
    public int key;
    public Node left, right;
 
    public Node(int key)
    {
        this.key = key;
        left = right = null;
    }
}
 
class GFG
{
public Node root;
 
// To calculate size of tree with given root 
public virtual int count(Node node)
{
    if (node == null)
    {
        return 0;
    }
 
    return count(node.left) +
           count(node.right) + 1;
}
 
// This function returns true if there 
// is an edge whose removal can divide 
// the tree in two halves n is size of tree 
public virtual bool checkRec(Node node, int n)
{
    // Base cases 
    if (node == null)
    {
        return false;
    }
 
    // Check for root 
    if (count(node) == n - count(node))
    {
        return true;
    }
 
    // Check for rest of the nodes 
    return checkRec(node.left, n) || 
           checkRec(node.right, n);
}
 
// This function mainly uses checkRec() 
public virtual bool check(Node node)
{
    // Count total nodes in given tree 
    int n = count(node);
 
    // Now recursively check all nodes 
    return checkRec(node, n);
}
 
// Driver code 
public static void Main(string[] args)
{
    GFG tree = new GFG();
    tree.root = new Node(5);
    tree.root.left = new Node(1);
    tree.root.right = new Node(6);
    tree.root.left.left = new Node(3);
    tree.root.right.left = new Node(7);
    tree.root.right.right = new Node(4);
    if (tree.check(tree.root) == true)
    {
        Console.WriteLine("YES");
    }
    else
    {
        Console.WriteLine("NO");
    }
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// Javascript program to check if 
// there exist an edge whose
// removal creates two trees of same size
     
     
    class Node
    {
        constructor(key)
        {
            this.key=key;
            this.left=this.right=null;
        }
    }
     
    // To calculate size of tree
    // with given root
    function count(node)
    {
        if (node == null)
            return 0;
          
        return count(node.left) +
        count(node.right) + 1;
    }
     
    // This function returns true 
    // if there is an edge
    // whose removal can divide the 
    // tree in two halves
    // n is size of tree
    function checkRec(node,n)
    {
        // Base cases
        if (node == null)
            return false;
  
        // Check for root
        if (count(node) == n - count(node))
            return true;
  
        // Check for rest of the nodes
        return checkRec(node.left, n)
                || checkRec(node.right, n);
    }
     
    // This function mainly uses checkRec()
    function check(node)
    {
        // Count total nodes in given tree
        let n = count(node);
  
        // Now recursively check all nodes
        return checkRec(node, n);
    }
     
    // Driver code
    let root = new Node(5);
    root.left = new Node(1);
    root.right = new Node(6);
    root.left.left = new Node(3);
    root.right.left = new Node(7);
    root.right.right = new Node(4);
    if(check(root)==true)
        document.write("YES");
    else
        document.write("NO"); 
     
    // This code is contributed by unknown2108
     
</script>

Output

YES

Time complexity: O(n²) where n is number of nodes in given Binary Tree.
Auxiliary Space: O(n) for call stack since using recursion, where n is no of nodes in binary tree

Method 2 (Efficient): We can find the solution in O(n) time. The idea is to traverse tree in bottom up manner and while traversing keep updating size and keep checking if there is a node that follows the required property.

Below is the implementation of above idea.

C++

// C++ program to check if there exist an edge whose
// removal creates two trees of same size
#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    int data;
    struct Node* left, *right;
};
 
// utility function to create a new node
struct Node* newNode(int x)
{
    struct Node* temp = new Node;
    temp->data = x;
    temp->left = temp->right = NULL;
    return temp;
};
 
// To calculate size of tree with given root
int count(Node* root)
{
    if (root==NULL)
        return 0;
    return count(root->left) + count(root->right) + 1;
}
 
// This function returns size of tree rooted with given
// root. It also set "res" as true if there is an edge
// whose removal divides tree in two halves.
// n is size of tree
int checkRec(Node* root, int n, bool &res)
{
    // Base case
    if (root == NULL)
       return 0;
 
    // Compute sizes of left and right children
    int c = checkRec(root->left, n, res) + 1 +
            checkRec(root->right, n, res);
 
    // If required property is true for current node
    // set "res" as true
    if (c == n-c)
        res = true;
 
    // Return size
    return c;
}
 
// This function mainly uses checkRec()
bool check(Node *root)
{
    // Count total nodes in given tree
    int n = count(root);
 
    // Initialize result and recursively check all nodes
    bool res = false;
    checkRec(root, n,  res);
 
    return res;
}
 
// Driver code
int main()
{
    struct Node* root = newNode(5);
    root->left = newNode(1);
    root->right = newNode(6);
    root->left->left = newNode(3);
    root->right->left = newNode(7);
    root->right->right = newNode(4);
 
    check(root)?  printf("YES") : printf("NO");
 
    return 0;
}

Java

// Java program to check if there exist an edge whose
// removal creates two trees of same size
 
class Node 
{
    int key;
    Node left, right;
 
    public Node(int key) 
    {
        this.key = key;
        left = right = null;
    }
}
 
class Res 
{
    boolean res = false;
}
 
class BinaryTree 
{
    Node root;
 
    // To calculate size of tree with given root
    int count(Node node) 
    {
        if (node == null)
            return 0;
 
        return count(node.left) + count(node.right) + 1;
    }
 
    // This function returns size of tree rooted with given
    // root. It also set "res" as true if there is an edge
    // whose removal divides tree in two halves.
    // n is size of tree
    int checkRec(Node root, int n, Res res) 
    {
        // Base case
        if (root == null)
            return 0;
        
        // Compute sizes of left and right children
        int c = checkRec(root.left, n, res) + 1
                + checkRec(root.right, n, res);
 
        // If required property is true for current node
        // set "res" as true
        if (c == n - c) 
            res.res = true;
 
        // Return size
        return c;
    }
 
    // This function mainly uses checkRec()
    boolean check(Node root) 
    {
        // Count total nodes in given tree
        int n = count(root);
 
        // Initialize result and recursively check all nodes
        Res res = new Res();
        checkRec(root, n, res);
 
        return res.res;
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(1);
        tree.root.right = new Node(6);
        tree.root.left.left = new Node(3);
        tree.root.right.left = new Node(7);
        tree.root.right.right = new Node(4);
        if (tree.check(tree.root) == true)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
 
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python3 program to check if there exist
# an edge whose removal creates two trees
# of same size
class Node:
     
    def __init__(self, x):
         
        self.key = x
        self.left = None
        self.right = None
 
# To calculate size of tree with 
# given root
def count(node):
     
    if (node == None):
        return 0
 
    return (count(node.left) +
            count(node.right) + 1)
 
# This function returns size of tree rooted 
# with given root. It also set "res" as true
# if there is an edge whose removal divides 
# tree in two halves.n is size of tree
def checkRec(root, n):
     
    global res
     
    # Base case
    if (root == None):
       return 0
 
    # Compute sizes of left and right children
    c = (checkRec(root.left, n) + 1 +
         checkRec(root.right, n))
 
    # If required property is true for 
    # current node set "res" as true
    if (c == n - c):
        res = True
 
    # Return size
    return c
 
# This function mainly uses checkRec()
def check(root):
     
    # Count total nodes in given tree
    n = count(root)
 
    # Initialize result and recursively 
    # check all nodes
    # bool res = false;
    checkRec(root, n)
 
# Driver code
if __name__ == '__main__':
     
    res = False
    root = Node(5)
    root.left = Node(1)
    root.right = Node(6)
    root.left.left = Node(3)
    root.right.left = Node(7)
    root.right.right = Node(4)
 
    check(root)
     
    if res:
        print("YES")
    else:
        print("NO")
 
# This code is contributed by mohit kumar 29

C#

// C# program to check if there exist an edge whose 
// removal creates two trees of same size 
using System;
 
public class Node
{
    public int key;
    public Node left, right;
 
    public Node(int key)
    {
        this.key = key;
        left = right = null;
    }
}
 
public class Res
{
    public bool res = false;
}
 
public class BinaryTree
{
    public Node root;
 
    // To calculate size of tree with given root 
    public virtual int count(Node node)
    {
        if (node == null)
        {
            return 0;
        }
 
        return count(node.left) + count(node.right) + 1;
    }
 
    // This function returns size of tree rooted with given 
    // root. It also set "res" as true if there is an edge 
    // whose removal divides tree in two halves. 
    // n is size of tree 
    public virtual int checkRec(Node root, int n, Res res)
    {
        // Base case 
        if (root == null)
        {
            return 0;
        }
 
        // Compute sizes of left and right children 
        int c = checkRec(root.left, n, res) + 1 + checkRec(root.right, n, res);
 
        // If required property is true for current node 
        // set "res" as true 
        if (c == n - c)
        {
            res.res = true;
        }
 
        // Return size 
        return c;
    }
 
    // This function mainly uses checkRec() 
    public virtual bool check(Node root)
    {
        // Count total nodes in given tree 
        int n = count(root);
 
        // Initialize result and recursively check all nodes 
        Res res = new Res();
        checkRec(root, n, res);
 
        return res.res;
    }
 
    // Driver code 
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(1);
        tree.root.right = new Node(6);
        tree.root.left.left = new Node(3);
        tree.root.right.left = new Node(7);
        tree.root.right.right = new Node(4);
        if (tree.check(tree.root) == true)
        {
            Console.WriteLine("YES");
        }
        else
        {
            Console.WriteLine("NO");
        }
    }
}
 
  // This code is contributed by Shrikant13

Javascript

<script>
// javascript program to check if there exist an edge whose
// removal creates two trees of same size
 
class Node {
 
    constructor(key) {
        this.key = key;
        this.left = this.right = null;
    }
}
 
class Res {
constructor(){
     this.res = false;
    }
}
 
 
    var root;
 
    // To calculate size of tree with given root
    function count( node) {
        if (node == null)
            return 0;
 
        return count(node.left) + count(node.right) + 1;
    }
 
    // This function returns size of tree rooted with given
    // root. It also set "res" as true if there is an edge
    // whose removal divides tree in two halves.
    // n is size of tree
    function checkRec( root , n,  res) {
        // Base case
        if (root == null)
            return 0;
 
        // Compute sizes of left and right children
        var c = checkRec(root.left, n, res) + 1 + checkRec(root.right, n, res);
 
        // If required property is true for current node
        // set "res" as true
        if (c == n - c)
            res.res = true;
 
        // Return size
        return c;
    }
 
    // This function mainly uses checkRec()
    function check( root) {
        // Count total nodes in given tree
        var n = count(root);
 
        // Initialize result and recursively check all nodes
         res = new Res();
        checkRec(root, n, res);
 
        return res.res;
    }
 
    // Driver code
     
         
        root = new Node(5);
        root.left = new Node(1);
        root.right = new Node(6);
        root.left.left = new Node(3);
        root.right.left = new Node(7);
        root.right.right = new Node(4);
        if (check(root) == true)
            document.write("YES");
        else
            document.write("NO");
 
// This code contributed by umadevi9616
</script>

Output

YES

Time Complexity: O(n)
Auxiliary Space: O(n)

A

Asaad Akram

Improve

Previous Article

Check if two nodes are cousins in a Binary Tree

Check whether a given binary tree is perfect or not

Similar Reads

Number of ways to divide a Binary tree into two halves

Given a binary tree, the task is to count the number of ways to remove a single edge from the tree such that the tree gets divided into two halves with equal sum.Examples: Input: 1 / \ -1 -1 \ 1 Output: 1 Only way to do this will be to remove the edge from the right of the root. After that we will get 2 sub-trees with sum = 0. 1 / -1 and -1 \ 1 wil

Check if max sum level of Binary tree divides tree into two equal sum halves

Given a Binary Tree, the task is to check if the maximum sum level divides the binary tree into the two parts of two equal sum halves.Examples: Input: 1 / \ 2 3 / \ \ 4 5 8 / \ 2 4 Output: YES Explanation: The maximum sum level is 2 and its sum is (4 + 5 + 8 = 17) Sum of the upper half (1 + 2 + 3) = 6 Sum of the Lower half (2 + 4) = 6 Input: 10 / \

Count number of ways to divide an array into two halves with same sum

Given an integer array of N elements. The task is to find the number of ways to split the array into two equal sum sub-arrays of non-zero lengths. Examples: Input: arr[] = {0, 0, 0, 0}Output: 3 Explanation:All the possible ways are: { {{0}, {0, 0, 0}}, {{0, 0}, {0, 0}}, {{0, 0, 0}, {0}} Therefore, the required output is 3. Input: {1, -1, 1, -1}Outp

Maximum cost of splitting given Binary Tree into two halves

Given a Binary Tree with N nodes valued 0 to N - 1 and N-1 edges and an array arr[] consisting of values of edges, the task is to find the maximum cost of splitting the tree into two halves. The cost of splitting a tree is equal to the product of sum of node values of the splitted subtrees. Examples: Input: N = 6, arr[] = {13, 8, 7, 4, 5, 9}, Edges

Difference between Tree edge and Back edge in graph

Tree Edge: It is an edge that is present in the tree obtained after performing DFS on the graph. All the Green edges are tree edges as shown in the below image. Back Edge: It is an edge (u, v) such that v is an ancestor of node u but not part of the DFS Traversal of the tree. Edge from 5 to 4 is a back edge. The presence of a back edge indicates a

Find Edge Weights in a Spanning Tree with Edge (u, v)

Given an undirected weighted graph with N nodes and M edges, the task is for each edge (u, v) find the minimum possible weight of the Spanning Tree which contains the edge (u, v). The edges are given in the form of a 2D array edges[][], such that edges[i] = {u, v, w} denotes that there is a directed edge from node u to node v with weight w. Example

Ways of dividing a group into two halves such that two elements are in different groups

Given 2n girls and randomly divided into two subgroups each containing n girls. The task is to count the number of ways in which groups can be formed such that two beautiful girls are into different groups.Example: Input: 4 Output: 4 Let group be r1, r2, b1, b2 where b1 and b2 are beautiful girls Groups are: ((r1, b1) (r2, b2)), ((r1, b2) (r2, b1))

Check if removing a given edge disconnects a graph

Given an undirected graph and an edge, the task is to find if the given edge is a bridge in graph, i.e., removing the edge disconnects the graph. Following are some example graphs with bridges highlighted with red color. Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. One solution is to find all bridges in given

Maximum weighted edge in path between two nodes in an N-ary tree using binary lifting

Given an N-ary tree with weighted edge and Q queries where each query contains two nodes of the tree. The task is to find the maximum weighted edge in the simple path between these two nodes.Examples: Naive Approach: A simple solution is to traverse the whole tree for each query and find the path between the two nodes.Efficient Approach: The idea i

Check if a line at 45 degree can divide the plane into two equal weight parts

Given a set of n points (xi, yi) in 2D coordinate. Each point has some weight wi. The task is to check whether a line at 45 degrees can be drawn so that sum of weights of points on each side is equal.Examples: Input : x1 = -1, y1 = 1, w1 = 3 x2 = -2, y2 = 1, w2 = 1 x3 = 1, y3 = -1, w3 = 4 Output : Yes Input : x1 = 1, y1 = 1, w1 = 2 x2 = -1, y2 = 1,

Article Tags :

DSA
Tree

Practice Tags :

Tree