Check sum of Covered and Uncovered nodes of Binary Tree - GeeksforGeeks
Given a binary tree, you need to check whether sum of all covered elements is equal to sum of all uncovered elements or not.
In a binary tree, a node is called Uncovered if it appears either on left boundary or right boundary. Rest of the nodes are called covered.
Read full article from Check sum of Covered and Uncovered nodes of Binary Tree - GeeksforGeeks
Given a binary tree, you need to check whether sum of all covered elements is equal to sum of all uncovered elements or not.
In a binary tree, a node is called Uncovered if it appears either on left boundary or right boundary. Rest of the nodes are called covered.
For calculating sum of Uncovered nodes we will follow below steps:
1) Start from root, go to left and keep going until left child is available, if not go to right child and again follow same procedure until you reach a leaf node.
1) Start from root, go to left and keep going until left child is available, if not go to right child and again follow same procedure until you reach a leaf node.
2) After step 1 sum of left boundary will be stored, now for right part again do the same procedure but now keep going to right until right child is available, if not then go to left child and follow same procedure until you reach a leaf node.
After above 2 steps sum of all Uncovered node will be stored, we can subtract it from total sum and get sum of covered elements and check for equines of binary tree.
int
sum(Node* t)
{
if
(t == NULL)
return
0;
return
t->key + sum(t->left) + sum(t->right);
}
/* Recursive function to calculate sum of left boundary
elements */
int
uncoveredSumLeft(Node* t)
{
/* If left node, then just return its key value */
if
(t->left == NULL && t->right == NULL)
return
t->key;
/* If left is available then go left otherwise go right */
if
(t->left != NULL)
return
t->key + uncoveredSumLeft(t->left);
else
return
t->key + uncoveredSumLeft(t->right);
}
/* Recursive function to calculate sum of right boundary
elements */
int
uncoveredSumRight(Node* t)
{
/* If left node, then just return its key value */
if
(t->left == NULL && t->right == NULL)
return
t->key;
/* If right is available then go right otherwise go left */
if
(t->right != NULL)
return
t->key + uncoveredSumRight(t->right);
else
return
t->key + uncoveredSumRight(t->left);
}
// Returns sum of uncovered elements
int
uncoverSum(Node* t)
{
/* Initializing with 0 in case we don't have
left or right boundary */
int
lb = 0, rb = 0;
if
(t->left != NULL)
lb = uncoveredSumLeft(t->left);
if
(t->right != NULL)
rb = uncoveredSumRight(t->right);
/* returning sum of root node, left boundry
and right boundry*/
return
t->key + lb + rb;
}
// Returns true if sum of covered and uncovered elements
// is same.
bool
isSumSame(Node *root)
{
// Sum of uncovered elements
int
sumUC = uncoverSum(root);
// Sum of all elements
int
sumT = sum(root);
// Check if sum of covered and uncovered is same
return
(sumUC == (sumT - sumUC));
}
Read full article from Check sum of Covered and Uncovered nodes of Binary Tree - GeeksforGeeks