Convert a binary tree to a sum tree / check if it is a sum tree

Medium

Problem

(1) Convert: replace each node's value with the sum of all values in its left and right subtrees (the original values); leaves become 0. (2) Check: return true if every non-leaf node already equals the sum of all nodes in its two subtrees.

Example 1

Input:  convert [10, -2, 6, 8, -4, 7, 5]
Output: [20, 4, 12, 0, 0, 0, 0]

Example 2

Input:  check [26, 10, 3, 4, 6, null, 3]
Output: true

Also asked as: Convert Binary tree into Sum tree · Check if Binary tree is Sum tree or not

Test cases

Case 1

Input:    [10,-2,6,8,-4,7,5]
Expected: [20,4,12,0,0,0,0]

Case 2

Input:    [1,2,3]
Expected: [5,0,0]

Case 3

Input:    [1]
Expected: [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Post-order: replace with children sum / verify equality

Time O(n)Space O(h)

Convert: return oldValue + newLeft + newRight, set node.val to newLeft + newRight. Check: a node is valid iff its value equals the sum of both subtrees (leaves count as valid).

function toSumTree(node) {
if (!node) return 0;
const old = node.val;
node.val = toSumTree(node.left) + toSumTree(node.right);
return node.val + old;
}
function isSumTree(node) {
if (!node || (!node.left && !node.right)) return true;
const treeSum = (n) => (n ? n.val + treeSum(n.left) + treeSum(n.right) : 0);
return node.val === treeSum(node.left) + treeSum(node.right) &&
isSumTree(node.left) && isSumTree(node.right);
}