Problem statement

Given the root of a binary tree, convert it in place into a sum tree: every node's new value is the sum of the original values of all nodes in its left and right subtrees. Leaves therefore become 0.

Return the root of the transformed tree.

Example 1

Input: root = [10,-2,6,8,-4,7,5]
Output: [20,4,12,0,0,0,0]
Explanation: The root's subtrees hold -2 + 8 - 4 = 2 and 6 + 7 + 5 = 18, so it becomes 20; -2 becomes 8 - 4 = 4, 6 becomes 12, and every leaf becomes 0.

Example 2

Input: root = [1]
Output: [0]
Explanation: A single leaf has nothing below it.

Example 3

Input: root = [3,1,null,2]
Output: [3,2,null,0]
Explanation: 3 becomes 1 + 2 = 3, 1 becomes 2, and the leaf 2 becomes 0.

Constraints

• 1 <= number of nodes <= 10^4
• -1000 <= Node.val <= 1000

Hints for Transform to Sum Tree

1. Hint 1

   A node's new value needs the totals of both subtrees, so the subtrees must be handled first — a post-order traversal.

2. Hint 2

   Let the recursion return the sum of the original values in the subtree it processed.

3. Hint 3

   At a node: remember its old value, set it to (left result + right result), and return old value + new value.

How to solve Transform to Sum Tree

Post-order recursion computes each subtree's total on the way back up. A node's new value is the total of its two subtrees, and the total it reports to its parent is that plus its own original value.

Approach

1. Define fold(node) returning the sum of the original values in node's subtree; fold(null) = 0.
2. At a node: save old = node.val, compute below = fold(left) + fold(right), set node.val = below.
3. Return old + below.
4. Call fold(root) and return root.

Why it works

When fold returns from a child, that child's subtree has been rewritten but the value returned is the sum of its original values, which is exactly what the parent's new value needs.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• Reading a child's value after it was rewritten gives its subtree sum without its own original value — return the original total instead.
• A leaf becomes 0, not its own value.

Reference solution

Python

from typing import Optional

def toSumTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    fold(root)
    return root

def fold(node: Optional[TreeNode]) -> int:
    # Rewrites the subtree and returns the sum of its original values.
    if node is None:
        return 0
    old = node.val
    node.val = fold(node.left) + fold(node.right)
    return old + node.val

Java

public static TreeNode toSumTree(TreeNode root) {
    fold(root);
    return root;
}

// Rewrites the subtree and returns the sum of its original values.
static int fold(TreeNode node) {
    if (node == null) return 0;
    int old = node.val;
    node.val = fold(node.left) + fold(node.right);
    return old + node.val;
}

C++

int fold(TreeNode* node);

TreeNode* toSumTree(TreeNode* root) {
    fold(root);
    return root;
}

// Rewrites the subtree and returns the sum of its original values.
int fold(TreeNode* node) {
    if (!node) return 0;
    int old = node->val;
    node->val = fold(node->left) + fold(node->right);
    return old + node->val;
}

JavaScript

var toSumTree = function(root) {
    fold(root);
    return root;
};

// Rewrites the subtree and returns the sum of its original values.
var fold = function(node) {
    if (node === null) return 0;
    var old = node.val;
    node.val = fold(node.left) + fold(node.right);
    return old + node.val;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy