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














































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
*/

More Articles of Ravi Kumar Prasad:

Name Views Likes
C++ std::is_enum 446 13
C++ Program to remove duplicate elements from std::list of integers 487 11
C++ std::lower_bound with std::vector 603 26
C++ ratio std::ratio::ratio_not_equal 464 26
C++ program to print bottom view of binary tree 409 14
C++ std::is_integral 752 23
C++ ratio std::ratio::ratio_greater_equal 431 18
C++ std::is_function 531 19
C++ ratio std::ratio::ratio_divide 494 21
C++ std::is_pointer 600 22
C++ std::is_floating_point 476 16
C++ program to check sum of covered and uncovered nodes of binary tree 626 28
C++ std::is_null_pointer 577 14
C++ ratio std :: ratio 1722 25
C++ std::upper_bound with std::vector 451 15
C++ std::is_empty 521 17
C++ std::equal with std::vector 460 19
C++ ratio std::ratio::ratio_less 454 16
C++ ratio std::ratio::ratio_multiply 456 17
C++ ratio std::ratio::ratio_add 453 20
C++ std::equal_range with std::vector 523 17
C++ ratio std::ratio::ratio_less_equal 405 16
C++ ratio std::ratio::ratio_greater 440 17
C++ program to insert an element into AVL tree 635 18
C++program to maximum sum of nodes in binary tree such that no two are adjacent 779 25
C++ ratio std::ratio::ratio_subtract 407 14
C++ ratio std::ratio::ratio_equal 392 20
C++ program to check if a given graph is tree or not 637 22
C++ program to find largest binary search tree in a Binary Tree 607 18
C++ program to find if the given vertical level of binary tree is sorted or not 436 20

Comments