In this tutorial we shall check if the tree is a sum tree or not.
Problem Statement:
You are given the root node of a binary tree. You need to check if that tree is a sum tree or not.
Example:
Consider the binary tree given below:
In the above image, it is a sum tree.
What is a sum tree?
A tree will be called as sum tree, if the parent node value is equal to the sum of it’s left sub tree and right sub tree.
For 1 and 2 parent node value is 3. That is the sum of 1 + 2
For 4 and 5 parent node value is 9, that is the sum of 4 + 5
For the root node value is 24, i.e it’s sum of left sub tree 3 + 2 + 1 = 6
and sum of right sub tree i.e 9 + 4 + 5 = 18.
By looking at the image, we can infer that, only the leaf node will not satisfy this condition.
But all the internal nodes need to satisfy this condition.
Solution in C++
#include <iostream>
#include <stack>
#include <map>
using namespace std;
// structure to hold binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
int check_is_sum_tree(Node* node)
{
// base case: empty tree
if (node == NULL)
return 0;
// leaf node
if (node->left == NULL && node->right == NULL)
return node->data;
if (node->data == check_is_sum_tree(node->left) + check_is_sum_tree(node->right))
return 2*node->data;
return INT_MIN;
}
int main()
{
Node* root = nullptr;
/* Binary tree:
16
/ \
/ \
10 25
/ \ / \
/ \ / \
7 15 18 30
*/
root = new Node(16);
root->left = new Node(10);
root->right = new Node(25);
root->left->left = new Node(7);
root->left->right = new Node(15);
root->right->left = new Node(18);
root->right->right = new Node(30);
if(check_is_sum_tree(root) != INT_MIN)
{
cout<<"It is a Sum tree"<<endl;
} else {
cout<<"It is not a sum tree"<<endl;
}
return 0;
}
Output:
It is not a sum tree
