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.

Examples :

Input:
    3
  /   \    
 1     2
Output: true
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 a sum tree.

Input:
          10
        /    \
      20      30
    /   \ 
   10    10
Output: false
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.

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

Constraints:
1 ≤ number of nodes ≤ 10⁵
1 ≤ node value ≤ 10⁵

Approach 01:

#include <iostream>
using namespace std;

class Solution {
public:
    bool isSumTree(Node* node) {
        return helper(node).second;
    }

private:
    pair<int, bool> helper(Node* node) {
        // Base case: If the node is NULL, it is a sum tree with sum 0
        if (node == NULL) {
            return {0, true};
        }

        // If the node is a leaf node, it is a sum tree with its own value
        if (node->left == NULL && node->right == NULL) {
            return {node->data, true};
        }

        // Recursively check the left and right subtrees
        auto left = helper(node->left);
        auto right = helper(node->right);

        // Check if the current node's value equals the sum of its left and right subtrees
        bool isSum = (node->data == left.first + right.first) && left.second && right.second;

        // Return the sum of the subtree rooted at the current node and whether it's a sum tree
        return {left.first + right.first + node->data, isSum};
    }
};

class Solution:
    def is_sum_tree(self, node):
        return self.helper(node)[1]

    def helper(self, node):
        # Base case: If the node is None, it is a sum tree with sum 0
        if node is None:
            return (0, True)

        # If the node is a leaf node, it is a sum tree with its own value
        if node.left is None and node.right is None:
            return (node.data, True)

        # Recursively check the left and right subtrees
        left = self.helper(node.left)
        right = self.helper(node.right)

        # Check if the current node's value equals the sum of its left and right subtrees
        isSum = (node.data == left[0] + right[0]) and left[1] and right[1]

        # Return the sum of the subtree rooted at the current node and whether it's a sum tree
        return (left[0] + right[0] + node.data, isSum)

Time Complexity

• Tree Traversal:

  The function helper performs a post-order traversal of the binary tree. It visits each node exactly once to compute the sum and check the sum tree property. Therefore, the time complexity is \( O(n) \), where \( n \) is the number of nodes in the tree.

Space Complexity

• Recursive Call Stack:

  The space complexity is determined by the maximum depth of the recursion stack. In the worst case, this depth is equal to the height of the tree. For a balanced tree, the height is \( O(\log n) \). For a skewed tree, the height can be \( O(n) \).

• Overall Space Complexity:

  The overall space complexity is \( O(h) \), where \( h \) is the height of the tree. In the worst case, the space complexity is \( O(n) \).