Convert Binary tree into Sum tree

The problem, simply

You get a binary tree of numbers. Change it in place: every node's new value is the total of the old values in its left subtree plus the old values in its right subtree. The node's own old value is not part of its new value.

Leaves have nothing below them, so they become 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Fix the tree from the top down. At each node, add up its whole left subtree and its whole right subtree first, while the old values are still there. Then change the node, and move down to the children.

1. If the node is empty, stop.
2. Compute total(left) and total(right) by walking those subtrees.
3. Set the node to their sum.
4. Do the same for the left child and the right child.

Going top down is important here: a node's children have not been changed yet when we add them up.

class Solution {
    public void toSumTree(TreeNode root) {
        if (root == null) return;
        root.val = total(root.left) + total(root.right);   // children still hold old values
        toSumTree(root.left);
        toSumTree(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: each 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

Go from the bottom up, and let each helper return the total of its old subtree. A parent then has everything it needs without walking down again.

1. An empty spot returns 0.
2. Ask the left child and the right child for their old totals, l and r.
3. Save the node's old value, then set the node to l + r.
4. Return old + l + r to the parent.

class Solution {
    public void toSumTree(TreeNode root) {
        convert(root);
    }

    // changes the subtree and returns the total of its OLD values
    private int convert(TreeNode n) {
        if (n == null) return 0;
        int l = convert(n.left);
        int r = convert(n.right);
        int old = n.val;
        n.val = l + r;            // leaves get 0 + 0
        return old + l + r;
    }
}

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

Watch out for

• Bottom up in Way 2, top down in Way 1. Mixing them up reads values that were already changed.
• Leaves need no special case. l and r are 0, so the leaf becomes 0 and returns its old value.
• Large sums can overflow int. Use long if the values are big.

What interviewers ask next

• Include the node's own value (each node becomes its whole subtree total)? Set n.val = old + l + r and return the same number.
• Check if a tree already is a sum tree? Same bottom up idea, but compare instead of overwrite. See "Check if a binary tree is a sum tree".
• Greater sum tree for a search tree (each node becomes the sum of all values greater than or equal to it)? Walk right, node, left, and keep a running sum (LeetCode 538).
• Without recursion? Do a post order walk with a stack, and keep the returned totals in a map from node to total.

Remember this

Grown-up words: the candy below you is the subtree sum, asking children first is post order traversal, changing the tree in place means no copy is made, and the waiting helpers are the call stack.