Introduction
A SumTree is a type of binary tree where the sum of the child subtrees is equal to the parent node. If there is no child node, i.e., a leaf node, that is also a SumTree. An empty binary tree can be considered a SumTree too.
Let’s discuss how to check if a given binary tree is a SumTree or not.
Problem Statement
In this problem, we have to check if a given binary tree is a SumTree.
Sample Examples
Example:
Input:
The given binary tree is
32
/ \
10 6
/ \ / \
8 2 3 3
Output: The given binary tree is a SumTree.
Explanation: The sum of the left and right subtrees of the root node is equal to the root node (16 = 10 + 6 + 8 + 2 + 3 + 3). Similarly, the sum of the subtrees for nodes 10 and 6 also equals their parent nodes. Therefore, it is a SumTree.
Brute Force Approach
In this approach, we store the root node and then get its subtrees. Check the sum of the subtrees and if it equals the root node. If it is, we continue recursively doing the same for the child nodes, and if it is not, then the binary tree is not a SumTree. If all the non-leaf nodes are equal to the sum of their subtrees, it will be a SumTree.
Steps of Algorithm
- First, we check for the case when the binary tree is empty. If it is, we declare it as a SumTree.
- We create a sum function that could recursively add all the values of the subtrees.
- Take the root node value and pass it through the sum function.
- Then check if the value returned by the sum function and the root node is the same. If it is not, the binary tree is not a SumTree. If it is, recursively pass the child nodes through the sum function and compare the values again.
- If the sum and parent node values are the same for all the non-leaf nodes, we have a SumTree.
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node* left;
struct node* right;
};
int sum(struct node *root) {
if (root == NULL)
return 0;
return sum(root->left) + root->data +
sum(root->right);
}
int SumTree(struct node* node) {
int ls, rs;
if (node == NULL ||
(node->left == NULL &&
node->right == NULL))
return 1;
ls = sum(node->left);
rs = sum(node->right);
if ((node->data == ls + rs) &&
SumTree(node->left) &&
SumTree(node->right))
return 1;
return 0;
}
struct node* newNode(int data) {
struct node* node = (struct node*)malloc(
sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main() {
struct node *root = newNode(32);
root->left = newNode(10);
root->right = newNode(6);
root->left->left = newNode(8);
root->left->right = newNode(2);
root->right->right = newNode(3);
root->right->left = newNode(3);
if (SumTree(root))
cout << "The given binary tree is a SumTree \n";
else
cout << "The given binary tree is not a SumTree \n";
getchar();
return 0;
}
Output:
The given binary tree is a SumTree
Complexity Analysis
Time Complexity: O(N2)
Explanation: In the worst-case scenario, the binary tree will be skewed to one side, so the time complexity is O(N2).
Space Complexity: O(N)
Explanation: In this approach, space is needed for every node, so the space complexity is O(N).