421. Maximum Sum of Non-Adjacent Nodes in a Binary Tree

Given a binary tree with positive node values, choose a subset of its nodes with no two chosen nodes directly connected by an edge (no chosen node may be the parent of another chosen node), maximizing the sum of chosen values, and print that maximum sum. 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); all node values are positive. Output: Print a single integer - the maximum sum achievable by choosing nodes with no two directly connected by an edge.

1 <= number of nodes <= 10^5

Returning a PAIR of values (included and excluded) from each recursive call, rather than just a single 'best' value, is the crucial technique - it's exactly what lets a parent correctly decide whether including itself is worth forcing its children to be excluded.

Pick a subset of a tree's nodes (no parent-child pair both chosen) that maximizes their total value. Brute force: Try every possible subset of nodes directly, checking the no-adjacent-pair constraint and computing sums - this is exponential in the number of nodes, completely impractical beyond tiny trees. Optimised: Returning BOTH the 'included' and 'excluded' best sums from every recursive call (rather than just one value) lets each parent correctly combine its children's best choices without ever needing to re-explore combinations - this is the exact same 'house robber on a tree' pattern, extending the array-based 'house robber' DP idea to tree structures.

Recursively consider every node with two independent choices - include it in the chosen subset or exclude it - and explore all combinations: if a node is included, its direct children must be excluded (though grandchildren are free), and if excluded, children can be freely included or excluded. Take the maximum sum over all valid combinations discovered this way. This exhaustively covers every valid subset satisfying the no-adjacent-nodes constraint, but the same node's best 'included'/'excluded' values get recomputed repeatedly across different branches of the recursion, causing exponential blowup. Time: O(2^n) worst case Space: O(h) recursion depth

Restructure the recursion so each call to a subtree directly returns a pair of values: the best sum if this node's own value is included, and the best sum if it is excluded, computed purely from the (include, exclude) pairs already returned by its two children (include = node.value + leftExclude + rightExclude; exclude = max(leftInclude, leftExclude) + max(rightInclude, rightExclude)). This computes every node's answer in one bottom-up post-order pass with no separate memo hashmap needed at all - the pair returned up the call stack is used immediately by the parent and then discarded - reducing auxiliary space from a full O(n) memo table down to just the O(h) recursion stack, while keeping the same linear time. Time: O(n) Space: O(h)

Keep the same recursive idea, but memoize the computed maximum sum for each node in a hashmap keyed by node reference the first time it's computed, and immediately return the cached value on any later call for that same node. Since every node's answer is now computed exactly once instead of being recomputed once per ancestor path, the total work becomes linear in the number of nodes, at the cost of maintaining an O(n)-sized memo table alongside the recursion. Time: O(n) Space: O(n) memo table + O(h) recursion stack

1. For every node, compute TWO values via post-order recursion: the best sum if this node IS included, and the best sum if it is NOT included. 2. If a node IS included, both its children must be EXCLUDED: included = node's value + excluded(left) + excluded(right). 3. If a node is NOT included, each child can independently be either included or excluded, so take the better of the two for each: excluded = max(included(left),excluded(left)) + max(included(right),excluded(right)). 4. The final answer is the larger of the root's own included/excluded values.

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

Test with a single-node tree, a small tree where choosing the root versus all its children changes the outcome, and a tree with 10^5 nodes for performance.

Be ready to connect this directly to 'House Robber III' (its well-known name in problem sets) and to the simpler array-based House Robber problem - recognizing the shared underlying pattern across array and tree versions is a valuable signal.