Sum Tree

Given a Binary Tree. Check for the Sum Tree for every node except the leaf node. Return true if it is a Sum Tree otherwise, return false.

A SumTree is a Binary Tree where the value of a node is equal to the sum of the nodes present in its left subtree and right subtree. 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.

?? View Full Code ??

Approach:

The most efficient way to solve this problem is to use a recursive post-order traversal. This approach allows us to calculate subtree sums from the bottom up, making it easier to check the sum property for each non-leaf node. Here’s a step-by-step breakdown of the approach:

1. Base Case: If the current node is None, we return 0 as the sum.If the node is a leaf, we return its value as it satisfies the Sum Tree condition by definition.
2. Recursive Post-Order Traversal: Recursively calculate the sum of the left and right subtrees. For each non-leaf node, check if its value is equal to the sum of the values of its left and right subtrees.
3. Return Sum and Validity: If a node violates the Sum Tree property, we return an invalid signal to stop further calculations. If all nodes meet the Sum Tree condition, we continue up the tree, accumulating sums to return the final result.

pair<bool,int>solve(Node* root){
        
        if(root == NULL){
            pair<bool,int>p = make_pair(true, 0);
            return p;
        }
        if(root->left == NULL && root->right == NULL){
            pair<bool,int>p = make_pair(true, root->data);
            return p;
        }
        
        pair<bool,int>left = solve(root->left);
        pair<bool,int>right = solve(root->right);
        
        bool isSumTreeNot = (root->data == left.second + right.second);
        
        bool check = left.first && right.first && isSumTreeNot;
        int sum = root->data + left.second + right.second;
        
        return make_pair(check, sum);
    }
    
    bool isSumTree(Node* root)
    {
        
        return solve(root).first;
    }        

Explanation :

• Base Conditions: We start by checking if the node is None or a leaf. If None, we return 0; if it’s a leaf, we return its value.
• Recursive Calls: We recursively calculate the sum of the left and right subtrees.
• Condition Check: For each non-leaf node, we verify if the node’s value equals the sum of its left and right subtree sums.
• Return Values: If a node violates the Sum Tree property, we return -1 to stop further checks.

Time Complexity : O(N)

Space Complexity : O(N)

?? View GitHub ??