 ### C++ program to check sum of covered and uncovered nodes of binary tree

/*
*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.
*So to find the sum of uncovered node we will find first the sum of the left boundary node and then sum of the right  boundary node.
1.Recursively go to the left node from the root node if left node is not null other wise we will go to
the right node and return the value of the node. This will give the sum of the left boundary node.
2.Recursively go to the right node from the root node if right node is not null other wise we will go to
the left node and return the value of the node. This will give the sum of the right boundary node.
*Now since we had not considered the root node value till now so the sum of the uncovered node is
SumOfUncoveredNode = SumOfLeftBoundryNode + SumOfRightBoundryNode + RootNodeValue
*Now to find sum of the covered node just find the sum of all node and subtract the sum of the uncovered node
*To find the sum of the all node I had used depth first search

*Example input
1
/  \
2    3
/      /  \
5     6   7
*Here the
Uncovered node is 1,2,3,5,7 so sum is 18
Covered node is 6 sum is 6
*/
#include <bits/stdc++.h> using namespace std; int sum_cover=0; int sum_uncover=0; struct Node { int value; struct Node* left, *right; }; //function to create the new node struct Node* newNode(int value) { Node* temp = new Node; temp->value = value; temp->left = temp->right = NULL; return temp; } //Function to calculate the sum of all node using breath first search int sum(Node* node) { if (node == NULL) return 0; return node->value + sum(node->left) + sum(node->right); } // Recursive function to calculate sum of left boundary int uncoveredSumLeft(Node* node) { /* If leaf node, then just return its value value */ if (node->left == NULL && node->right == NULL) return node->value; /* If left is available then go left otherwise go right */ if (node->left != NULL) return node->value + uncoveredSumLeft(node->left); else return node->value + uncoveredSumLeft(node->right); } //Recursive function to calculate sum of right boundary int uncoveredSumRight(Node* node) { /* If leaf node, then just return its value value */ if (node->left == NULL && node->right == NULL) return node->value; /* If right is available then go right otherwise go left */ if (node->right != NULL) return node->value + uncoveredSumRight(node->right); else return node->value + uncoveredSumRight(node->left); } //function to find sum of the uncovered node and sum of the covered node void findSumOfCoverUncoverNode(Node *root){ //get sum of the left boundry if (root->left != NULL) sum_uncover += uncoveredSumLeft(root->left); //get sum of the right boundry node and with sum of the left boundry if (root->right != NULL) sum_uncover += uncoveredSumRight(root->right); // add the root value to the sum of the uncover sum_uncover += root->value; //sum of the covered node sum_cover = sum(root) - sum_uncover; } // Driver program to test above functions int main() { // Input for the above given diagram's binary tree Node* root = newNode(1); root->left = newNode(2); root->left->right = newNode(5); root->right = newNode(3); root->right->right = newNode(7); root->right->left = newNode(6); //function call to find the sum of the covered node and sum of the uncovered node findSumOfCoverUncoverNode(root); cout<<"Sum of Uncovered node "<<sum_uncover<<endl<<"Sum of Covered node "<<sum_cover<<endl; return 0; }
/*
OUTPUT:-
Sum of Uncovered node 18
Sum of Covered node 6
*/ 