#### Tree

Problem
Check if the given tree is a sum tree i.e value at each node is equal to the value of all elements in its left subtree and right subtree. The Binary tree shown below is an example of a sumtree.

Solution
Suppose we start at root node ( X ). We can compute the sum of the node values of left subtree ( sum1 ) and right subtree ( sum2 ). If X -> data = sum1 + sum2 and the same condition is true for each node in the left and right subtrees, then the given tree is a sum tree. See the implementation below.

```#include<iostream>
using namespace std;

// tree node structure
typedef struct tree_node {
int value;
struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
node *new_node = new node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

// create the tree
node *createTree() {
node *root = getNewNode(30);
root->left = getNewNode(12);
root->right = getNewNode(3);
root->left->left = getNewNode(5);
root->left->right = getNewNode(7);
root->right->left = getNewNode(1);
root->right->right = getNewNode(2);
return root;
}

// get the sum of all elements in the subtree starting at a given node
int getSubtreeSum(node *ptr) {
if (ptr == NULL) {
return 0;
}
else {
return getSubtreeSum(ptr->left) + ptr->value + getSubtreeSum(ptr->right);
}
}

// check if the given tree is a sum tree i.e value at each node is equal to
// the value of all elements in left subtree and right subtree
bool isSumTree(node *ptr) {
if (ptr == NULL || (ptr->left==NULL && ptr->right==NULL))
return true;
int left_subtree_sum = getSubtreeSum(ptr->left);
int right_subtree_sum = getSubtreeSum(ptr->right);
if (ptr->value == (left_subtree_sum + right_subtree_sum)
&& isSumTree(ptr->left) && isSumTree(ptr->right)) {
return true;
}
else {
return false;
}
}

// main
int main() {
node *root = createTree();
if (isSumTree(root))
cout<<"The given tree is a SumTree ";
else
cout<<"The given tree is not a SumTree ";
cout<<endl;
return 0;
}```