Sum Tree

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Check if binary tree is a Sum Tree (each node = sum of all nodes in left and right subtrees).

Algorithm

1For each node: compute subtree sum. If node.val == leftSum + rightSum: continue. Else false.

Common Pitfalls

•Post-order DFS. Return subtree sum. At each node: check val == left_sum + right_sum.

Sum Tree.java

Java

// Approach: DFS. Verify each node = sum of all values in its left and right subtrees.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {
    boolean ans = true;

    boolean isSumTree(Node root) {
        solve(root);
        return ans;
    }

    int solve(Node root) {
        if (root == null)
            return 0;

        int left = solve(root.left);
        int right = solve(root.right);

        if ((root.left != null || root.right != null) && left + right != root.data)
            ans = false;

        return root.data + left + right;
    }
}

Was this solution helpful?