Check if removing an edge can divide a Binary Tree in two halves - GeeksforGeeks
Given a Binary Tree, find if there exist edge whose removal creates two trees of equal size.
O(n2)
Read full article from Check if removing an edge can divide a Binary Tree in two halves - GeeksforGeeks
Given a Binary Tree, find if there exist edge whose removal creates two trees of equal size.
Input : root of following tree 5 / \ 1 6 / / \ 3 7 4 Output : true Removing edge 5-6 creates two trees of equal size
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.
// 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;
}
O(n2)
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.
// 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);
}