#include <iostream>
using namespace std;

struct Node           //we are creating a basic node with pointers to its left and right nodes
{ 
    int data;
    struct Node *left;
    struct Node *right;
};

int sum_of_nodes(struct Node* node)  //this is a function to find the sum of the nodes and its left and right nodes
{

   if(node==NULL)
       return 0;

   return(sum_of_nodes(node->left)+node->data+sum_of_nodes(node->right));
}

int check_sum_tree(struct Node* node)  //recursive function which checks whether the current node is a sum tree or not
{
 
    if(node==NULL||node->left==NULL && node->right==NULL)  //if the node has no left or right branches, it is a sum tree
        return 1;


    int left_sum=sum_of_nodes(node->left);                   /*getting the sums of the left
                                                         and right nodes of the root node provided*/
    int right_sum=sum_of_nodes(node->right);
    if(node->data==(left_sum+right_sum) && check_sum_tree(node->left) && check_sum_tree(node->right))
         return 1;

    return 0;


}

struct Node* insert_node(int value)                    //function to create a new node in the tree 
{

    Node *node=new Node;
    node->data=value;
    node->left=NULL;
    node->right=NULL;

    return node;

}

int main()
{
   /*         The tree structure we have taken as an example here is:
                    
                                      40
                                     /   
                                    10  10
                                   /   / 
                                  5   5 4  6
  */



    Node *node  = insert_node(40); 
    node->left         = insert_node(10); 
    node->right        = insert_node(10); 
    node->left->left   = insert_node(5); 
    node->left->right  = insert_node(5); 
    node->right->right = insert_node(4);
    node->right->left = insert_node(6); 


if(check_sum_tree(node))
    cout<<"The tree is a sum tree\n";
else
    cout<<"the tree is not a sum tree\n";
return 0;
}