### c++ program to check if a given tree is a sum tree

C++ PROGRAM TO CHECK IS A GIVEN BINARY TREE IS A SUM TREE

A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0.

The binary trees on the left are sum trees as                                                                      mentioned in the above definition.

``#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;}``
The check_sum_tree function recursively checks if the left and right nodes of the root indiviually form binary sum tree or not.

INPUT: we check with a custom input
OUTPUT: The tree is a sum tree

TIME COMPLEXITY:

O(n^2) in the worst case.