412. Convert a Binary Tree Into a Sum Tree

Given a binary tree, replace every node's value with the sum of the values in its left and right subtrees (not counting the node's own original value); every leaf becomes 0. Print the resulting tree using level-order tokens. Print the resulting tree the same way (level order, 'N' for absent children), but omit any trailing 'N' tokens at the very end of your output. Node values may be negative.

Input: A single line of space-separated level-order tokens ('N' for missing children) describing the binary tree; node values may be negative. Output: Print the resulting sum tree's level-order tokens ('N' for absent children) on one line, omitting trailing 'N' tokens.

1 <= number of nodes <= 10^5

This problem explicitly allows NEGATIVE values - the sum computation must handle this correctly with no special-casing needed, since simple addition already handles negatives correctly.

Replace every node's value with the sum of ALL the values in its subtrees (not counting its own original value) - every leaf becomes 0. Brute force: For every node, separately re-traverse its entire subtree from scratch to compute the sum of everything beneath it - this recomputes overlapping sums repeatedly, costing O(n²) in the worst case. Optimised: A single post-order pass that RETURNS the total original-value sum of a subtree (for use by the parent) while SIMULTANEOUSLY overwriting the current node's displayed value, computes everything needed in one traversal with no repeated work - the classic 'return one thing, mutate another' pattern for tree post-order problems.

For every node, write a helper that independently traverses its entire left subtree to total it, then its entire right subtree to total it, and assign the node's new value as that combined total; recurse this same process down into the children afterward. Because the helper re-walks a whole subtree from scratch for every single node in the tree rather than reusing work already done for descendants, the same nodes get visited repeatedly, making this quadratic in the worst case (e.g. a skewed tree). Time: O(n^2) Space: O(h)

First do one post-order traversal that computes and stores, for every node, the sum of its original subtree values in a hash map (without modifying anything yet). Then do a second traversal that sets each node's new value to storedSum[left child] + storedSum[right child], using the untouched original sums looked up from the map. This needs two full passes and extra map storage, but each node's sum is computed exactly once instead of being recomputed by ancestors. Time: O(n) Space: O(n)

Do one recursive post-order traversal where each call first recurses into the left and right children (which, as a side effect, already convert them into sum trees and return the sum of their original subtree), saves the current node's original value locally, overwrites the node's value with leftReturn + rightReturn, and returns leftReturn + rightReturn + the saved original value up to its parent. This way each node is visited exactly once and no extra storage beyond the recursion stack is needed, since the needed subtree totals are threaded through return values instead of being stored or recomputed. Time: O(n) Space: O(h)

1. Do a post-order traversal: fully convert both children FIRST, before touching the current node. 2. A helper function returns 'the total sum of everything in this subtree using the ORIGINAL values', while ALSO overwriting each node's value with its children's combined original sums along the way. 3. A leaf's 'children sum' is 0 by definition (it has no children) - that's exactly why leaves become 0.

Time: O(n) - one single post-order pass. Space: O(h) for the recursion stack.

Test a single-node tree (it becomes 0, since a leaf has no children to sum), a tree containing negative values, and n=10^5 nodes for performance.

Be careful to use each node's ORIGINAL value when computing sums to return upward, even though the node's DISPLAYED value has already been overwritten - mixing up original versus already-overwritten values is the most common bug here.