Check sum of Covered and Uncovered nodes of Binary Tree | C ++ program to find sum of Covered and Uncovered node of binary tree ; A binary tree node has key , pointer to left child and a pointer to right child ; To create a newNode of tree and return pointer ; Utility function to calculate sum of all node of tree ; Recursive function to calculate sum of left boundary elements ; If leaf node , then just return its key value ; If left is available then go left otherwise go right ; Recursive function to calculate sum of right boundary elements ; If leaf node , then just return its key value ; If right is available then go right otherwise go left ; Returns sum of uncovered elements ; Initializing with 0 in case we don 't have  left or right boundary  ; returning sum of root node , left boundary and right boundary ; Returns true if sum of covered and uncovered elements is same . ; Sum of uncovered elements ; Sum of all elements ; Check if sum of covered and uncovered is same ; Helper function to print inorder traversal of binary tree ; Driver program to test above functions ; Making above given diagram 's binary tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; struct Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } int sum ( Node * t ) { if ( t == NULL ) return 0 ; return t -> key + sum ( t -> left ) + sum ( t -> right ) ; } int uncoveredSumLeft ( Node * t ) { if ( t -> left == NULL && t -> right == NULL ) return t -> key ; if ( t -> left != NULL ) return t -> key + uncoveredSumLeft ( t -> left ) ; else return t -> key + uncoveredSumLeft ( t -> right ) ; } int uncoveredSumRight ( Node * t ) { if ( t -> left == NULL && t -> right == NULL ) return t -> key ; if ( t -> right != NULL ) return t -> key + uncoveredSumRight ( t -> right ) ; else return t -> key + uncoveredSumRight ( t -> left ) ; } int uncoverSum ( Node * t ) { int lb = 0 , rb = 0 ; if ( t -> left != NULL ) lb = uncoveredSumLeft ( t -> left ) ; if ( t -> right != NULL ) rb = uncoveredSumRight ( t -> right ) ; return t -> key + lb + rb ; } bool isSumSame ( Node * root ) { int sumUC = uncoverSum ( root ) ; int sumT = sum ( root ) ; return ( sumUC == ( sumT - sumUC ) ) ; } void inorder ( Node * root ) { if ( root ) { inorder ( root -> left ) ; printf ( " % d ▁ " , root -> key ) ; inorder ( root -> right ) ; } } int main ( ) { Node * root = newNode ( 8 ) ; root -> left = newNode ( 3 ) ; root -> left -> left = newNode ( 1 ) ; root -> left -> right = newNode ( 6 ) ; root -> left -> right -> left = newNode ( 4 ) ; root -> left -> right -> right = newNode ( 7 ) ; root -> right = newNode ( 10 ) ; root -> right -> right = newNode ( 14 ) ; root -> right -> right -> left = newNode ( 13 ) ; if ( isSumSame ( root ) ) printf ( " Sum ▁ of ▁ covered ▁ and ▁ uncovered ▁ is ▁ same STRNEWLINE " ) ; else printf ( " Sum ▁ of ▁ covered ▁ and ▁ uncovered ▁ is ▁ not ▁ same STRNEWLINE " ) ; }