414. Check if a Binary Tree Is a Sum Tree

Given a binary tree, print 'Yes' if it is a sum tree - meaning every node's value equals the sum of all values in its left subtree plus all values in its right subtree (a leaf is always trivially a sum tree) - otherwise print 'No'. 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). Output: Print 'Yes' if the tree is a sum tree, otherwise print 'No'.

1 <= number of nodes <= 10^5

A leaf node passing 'trivially' (with no children to sum) is the essential base case that makes the whole recursive definition well-founded - without it, the recursion would have no valid starting point.

Check whether every node's value equals the sum of all values in its entire left subtree plus its entire right subtree. Brute force: For every node, separately compute the total sum of its left and right subtrees from scratch by re-traversing them each time - this recomputes the same sums repeatedly, costing O(n²) in the worst case. Optimised: A single post-order recursive pass that RETURNS each subtree's total sum while validating the current node on the way back up computes everything needed in one traversal - no re-computation of any subtree's sum happens more than once.

Do the computation and the verification in the very same post-order traversal: a recursive helper on a node first recurses on the left and right children, getting back both their subtree sum and whether they are valid sum trees, then combines them - the current node's subtree sum is its value plus both children's sums (or just its own value if it's a leaf), and it is itself a valid sum tree only if both children are valid and its value equals the sum of their subtrees. Returning both pieces of information together means each node is visited exactly once with no extra storage beyond the call stack, which is the natural minimum for a tree problem. Time: O(n) Space: O(h) recursion stack, h = tree height

First do one post-order traversal that computes and stores the total sum of every subtree (keyed by node) in a hash map, visiting each node exactly once. Then do a second traversal that, for every node, looks up the already-computed sums of its left and right children in the map (an O(1) lookup) and checks whether the node's value matches their total. Storing the subtree sums avoids ever recomputing a sum that was already found, bringing the total work down to linear, at the cost of the extra map to hold every subtree's sum. Time: O(n) Space: O(n)

For every node in the tree, independently walk its entire left subtree and its entire right subtree to compute their sums from scratch, then check whether the node's value equals that combined sum, recursing to do the same check at every other node too. This is a direct, correct implementation of the sum-tree definition, but summing a subtree from scratch for every single node means the same lower nodes get re-added into a sum many times as the check climbs up the tree, giving quadratic total work in the worst case (e.g. a skewed tree). Time: O(n^2) Space: O(h) recursion stack, h = tree height

1. Write a recursive helper that, for each node, returns the TOTAL sum of its entire subtree (including itself). 2. On the way back up from each recursive call, check whether the current node's own value equals the sum returned by its left subtree plus the sum returned by its right subtree. 3. A leaf node automatically satisfies the rule (there's nothing to sum, so it trivially passes) - if any node ever fails the check, the whole tree is not a sum tree.

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

Test with a single-node tree (trivially a sum tree), a node with only one child present (its value must still equal that lone subtree's sum), and a tree with 10^5 nodes for performance.

Be ready to explain why 'return the sum while also checking' (doing both jobs in one recursive call) is more efficient than two separate passes (one to compute sums, one to check) - combining them is the key efficiency insight.