# Check if a given Binary Tree is SumTree in C++

In this tutorial, we are going to learn how to check for a SumTree in a Binary Tree using C++. If the value of each node in a Binary Tree is equal to the sum of all the nodes present in its left and right subtrees then the tree is called a SumTree.

**Example of a SumTree:**

If the root of a subtree in a SumTree has at least one child then the sum of the values of all nodes in the subtree is equal to twice the value of the root. In the above example, as the binary tree is a SumTree the sum of all the nodes is equal to twice the value of the root.

20*2 = 20 + 3 + 7 + 1 + 2 + 3 + 4

Using the above observation we will implement a recursive function that checks if a given Binary Tree is a SumTree.

## Implementing a function to check if a Binary Tree is Sum Tree

**Recursive Function**

isSumTree(root)

- If the node is empty or if the node is a leaf node return True.
- Assume that the left subtree and right subtree are SumTrees and find the sum of the nodes in the left subtree and the right subtree.
- Check if the current subtree is a SumTree.
- Verify if the left subtree and right subtree are SumTrees by making the recursive function call on them.
- If the above two conditions are satisfied return True or else return False.

#include <bits/stdc++.h> using namespace std; struct Node{ int data; Node* left; Node* right; Node(int val){ data = val; left = NULL,right = NULL; } }; int sumOfSubTree(Node* node){ if(node == NULL){ return 0; } // Checking if the node is a leaf node else if(node->left == NULL && node->right == NULL){ return node->data; } else{ return 2*(node->data); } } bool isSumTree(Node* node){ if(node == NULL || (node->left == NULL && node->right == NULL)){ return true; } int l,r; /* Assume that the left and right subtrees are SumTrees and get the sum of nodes in left and right subtrees respectively */ l = sumOfSubTree(node->left); r = sumOfSubTree(node->right); /* Check if the current subtree is a SumTree and also verify if the left and right subtrees are also SumTrees */ if(node->data == (l+r) && isSumTree(node->left) && isSumTree(node->right)){ return true; } else{ return false; } } int main(){ struct Node* root = new Node(20); root->left = new Node(3); root->right = new Node(7); root->left->left = new Node(1); root->left->right = new Node(2); root->right->left = new Node(3); root->right->right = new Node(4); if(isSumTree(root)){ cout<<"The given Binary Tree is a SumTree"<<endl; } else{ cout<<"The given Binary Tree is not a SumTree"<<endl; } }

**Output:**

The given Binary Tree is a SumTree

**sumOfSubTree()** function takes the root of subtree as an argument and returns the sum of nodes in the subtree.

**Time Complexity:** O(n)

We hope you got a clear idea of how to check if a given Binary tree is SumTree in C++.

## Leave a Reply

You must be logged in to post a comment.