Check if Binary tree is Sum tree or not

The problem, simply

You get a binary tree of numbers. It is a sum tree if every node that has children holds exactly the total of all the nodes in its left subtree plus all the nodes in its right subtree. Leaves are fine on their own, and an empty side counts as 0.

Answer true if the whole tree is a sum tree.

A story to remember it

Picture it

Examples

Way 1: the simple way

At every node with children, add up its whole left subtree and its whole right subtree from scratch, and compare. Then check both children the same way.

1. An empty node or a leaf is fine.
2. Compute total(left) and total(right) by walking those subtrees.
3. The node must equal their sum, and both children must pass too.

class Solution {
    public boolean isSumTree(TreeNode root) {
        if (root == null) return true;
        if (root.left == null && root.right == null) return true;   // a leaf is fine
        int left = total(root.left);
        int right = total(root.right);
        return root.val == left + right && isSumTree(root.left) && isSumTree(root.right);
    }

    private int total(TreeNode n) {
        if (n == null) return 0;
        return n.val + total(n.left) + total(n.right);
    }
}

How long it takes: every node adds up everything below it again. In a stick shaped tree that is about n * n / 2 steps, O(n^2). Extra room: the waiting helpers, O(h).

Way 2: the clever way

Add up totals once, from the bottom up. Each helper returns the total of its whole subtree, and checks its own label on the way.

1. An empty node returns 0.
2. A leaf returns its value.
3. Otherwise get l from the left and r from the right. If the node is not equal to l + r, remember that the answer is false.
4. Return node + l + r so the parent can use it.

class Solution {
    private boolean ok;

    public boolean isSumTree(TreeNode root) {
        ok = true;
        total(root);
        return ok;
    }

    // returns the total of every node in this subtree
    private int total(TreeNode n) {
        if (n == null || !ok) return 0;
        if (n.left == null && n.right == null) return n.val;   // a leaf
        int l = total(n.left);
        int r = total(n.right);
        if (n.val != l + r) ok = false;                         // wrong label
        return n.val + l + r;
    }
}

How long it takes: each node is visited once, O(n). Extra room: the waiting helpers, O(h).

Watch out for

• Comparing only with the children's values. The label must equal the whole subtree, not just the two children. In the first example 26 is not 10 + 3.
• Treating a leaf as wrong because it is not 0 + 0. Leaves are fine by definition.
• Big totals can overflow int. Use long if the values are large.

What interviewers ask next

• Why does a passing node always return twice its value? Because its total is node + l + r and l + r equals node. Some solutions return 2 * node for that reason.
• Turn any tree into a sum tree? Replace each node with the total of its subtrees, from the bottom up. That is the "convert to sum tree" problem.
• Count how many subtrees are sum trees? Return both the total and a flag from each helper, and count the flags.

Remember this

Grown-up words: the piggy bank labels are node values, the totals are subtree sums, children before parents is post order traversal, and the -1 trick is a sentinel value.