Problem Statement

Given a Binary Tree. Return 1 if, for every node X in the tree other than the leaves, its value is equal to the sum of its left subtree's value and its right subtree's value. Else return 0.

An empty tree is also a Sum Tree as the sum of an empty tree can be considered to be 0. A leaf node is also considered a Sum Tree.

Example 1:

Input:
    3
  /   \\
 1     2

Output: 1
Explanation:The sum of left subtree and right subtree
is 1 + 2 = 3, which is the value of the root node.
Therefore,the given binary tree is asum tree.

Example 2:

Input:          
          10
        /    \\
      20      30
    /   \\
   10    10

Output:0
Explanation:The given tree is not a sum
tree. For the root node, sum of elements
in left subtree is 40 and sum of elements
in right subtree is 30. Root element = 10
which is not equal to 30+40.

Your Task: You dont need to read input or print anything. Complete the function isSumTree() which takes root node as input parameter and returns true if the tree is a SumTree else it returns false.

Expected Time Complexity: O(N)Expected Auxiliary Space: O(Height of the Tree)

Problem Link

Check if a given Binary Tree is SumTree - GeeksforGeeks

Code

Naive Approach :

Get the sum of nodes in the left subtree and right subtree. Check if the sum calculated is equal to the root’s data. Also, recursively check if the left and right subtrees are SumTrees.

/*  Tree node
struct Node
{
    int data;
    Node* left, * right;
}; */

// Should return true if tree is Sum Tree, else false
class Solution
{
    public:
    bool isSumTree(Node* root)
    {
         if(!root)
         return true;
         
        if(!root->left&&!root->right)
        return true;
        
        bool lst = isSumTree(root->left);
        bool rst = isSumTree(root->right);
        
        
        
        return lst&&rst&&root->data==solve(root->left)+solve(root->right);
        
         
    }
    int solve(Node* root)
    {
        if(!root)
        return 0;
        
        if(!root->left&&!root->right)
        return root->data;
        
        int leftsum = solve(root->left);
        int rightsum = solve(root->right);
        
        return leftsum+rightsum+root->data;;
    }
};
// Time Complexity : O(n^2) (worst case)

Optimized Approach:

Method 1 uses sum() to get the sum of nodes in left and right subtrees. Method 2 uses the following rules to get the sum directly.

1. If the node is a leaf node then the sum of the subtree rooted with this node is equal to the value of this node.

2. If the node is not a leaf node then the sum of the subtree rooted with this node is twice the value of this node (Assuming that the tree rooted with this node is SumTree).