420. Find the Largest Subtree Sum in a Binary Tree

Given a binary tree, find the maximum sum of node values among all of its subtrees (every node roots exactly one subtree, including the whole tree itself and every single leaf), and print it. Node values may be negative. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens describing the binary tree ('N' marks an absent child); node values may be negative. Output: Print a single integer - the maximum subtree sum found anywhere in the tree.

1 <= number of nodes <= 10^5

This is structurally almost identical to 'Kadane's algorithm' extended from arrays to trees - both track a best-value-seen-so-far while computing a value that must be RETURNED upward for use by the parent computation.

Find the maximum possible sum of node values among all of a tree's subtrees, where values might be negative. Brute force: For every node, separately traverse its ENTIRE subtree to compute its sum from scratch - this recomputes overlapping sums many times, costing O(n²) in the worst case. Optimised: A single post-order pass computes and returns each node's subtree sum exactly once, reusing already-computed child sums directly rather than re-traversing - tracking a running 'best sum seen so far' as a side effect of this same pass finds the answer with zero extra traversals.

Do a single post-order traversal where each recursive call returns the sum of its own subtree (computed once from its children's already-returned sums, not recomputed from scratch), appending every computed subtree sum to an auxiliary list as it is produced. After the traversal finishes, scan the list once to find the maximum. This computes every subtree sum in linear time instead of quadratic, at the cost of storing all of them. Time: O(n) Space: O(n)

For every node in the tree, run a fresh traversal of the subtree rooted there to compute its sum, and keep the maximum sum found across all nodes. This correctly checks every possible subtree by definition, but recomputing each subtree's sum from scratch means work is repeated many times over (a node near the root gets its descendants' sums recomputed for every ancestor above it), giving quadratic behavior in the worst case such as a skewed tree. Time: O(n^2) Space: O(h)

Do the same single post-order traversal, returning each subtree's sum computed from its children, but instead of storing every sum in a list, compare it against a single running maximum variable (accessible across the recursion, e.g. by reference or as a return alongside the sum) and update it in place whenever a larger subtree sum is found. This produces the identical answer as storing all sums, but without needing an auxiliary list, leaving only the recursion stack as extra space. Time: O(n) Space: O(h)

1. Compute every subtree's total sum bottom-up, using a single post-order pass. 2. A node's own subtree sum is its own value plus its left subtree's sum plus its right subtree's sum - a value you need to return upward anyway for the parent's calculation. 3. Track the maximum subtree sum seen at ANY node throughout this entire process.

Time: O(n) - one single post-order pass, computing every subtree sum exactly once. Space: O(h) for the recursion stack.

Test with all-negative values (answer is whichever single node is least negative), a single-node tree, a case where the whole tree's total is the maximum, and a tree with 10^5 nodes for performance.

Be ready to handle the all-negative-values edge case explicitly - the answer then becomes whichever single node's value is least negative, since a smaller (less negative) subtree naturally beats combining in more negative values.