119. Maximum Root-to-Leaf Path Sum

Given a binary tree, find the maximum sum along any path from the root to a leaf. 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 ('N' for missing children) describing the binary tree. Output: Print a single integer - the maximum sum along any root-to-leaf path.

1 <= number of nodes <= 10^5

This must end at a LEAF specifically, not just any node - a subtle but important constraint distinguishing this from the more general 'maximum path sum between any two nodes' problem.

Find the largest possible sum along any path starting at the root and ending at a leaf. Brute force: Enumerate every possible root-to-leaf path explicitly, summing each one, then take the maximum - this works but requires tracking and summing full paths, when a bottom-up recursive combination avoids ever needing to materialize the paths themselves. Optimised: A single post-order recursive pass, where each node returns the best achievable sum from itself down to any leaf beneath it, lets a parent directly combine its own value with the BETTER of its children's results - no need to explicitly enumerate or store full paths.

Use the same running-sum idea as the recursive approach, but manage it with an explicit stack of (node, sum-so-far) pairs instead of relying on the language's call stack: push the root with its own value, and repeatedly pop a node, update the best answer if it's a leaf, or push its children with the running sum extended by their values. This computes the identical result in the same time and space as the recursive version, but removes the risk of a stack overflow crash on a deeply skewed tree, which matters given the problem allows up to 10^5 nodes in a single chain. Time: O(n) Space: O(h)

Recursively descend the tree while carrying along a single running sum (the total from the root down to the current node) as a parameter, rather than storing the whole path; when a leaf is reached, compare the running sum to the best found so far and update it if larger. This computes the same answer without ever materializing full path lists, so each node contributes only constant extra work, cutting the total time and space down from the brute force's path-length-dependent blowup to something driven purely by the number of nodes and the recursion depth. Time: O(n) Space: O(h)

Rebuild the tree, then recursively explore every root-to-leaf path, explicitly building and storing the list of node values along each path as it is discovered; once a leaf is reached, sum that stored path and compare it against the best sum seen so far. This is correct since every path is examined, but explicitly copying and storing each path's values costs extra time and memory proportional to the path length, which for a skewed tree can make the total work quadratic. Time: O(n*h) Space: O(n*h)

1. Recursively compute the best root-to-leaf sum achievable from each subtree. 2. A LEAF's best sum is simply its own value. 3. An INTERNAL node's best sum is its own value plus the LARGER of its two children's best sums (only recursing into children that actually exist).

Time: O(n) - one single post-order pass, computing each node's best downward sum exactly once. Space: O(h) for the recursion stack.

Test a single-node tree (answer is that node's own value), a node with only one child (the path must follow the existing child, since there is no leaf on the missing side), and n=10^5 nodes for performance.

Be careful with a node that has only ONE child - it MUST use that child's path (since there's no leaf directly reachable through the missing side), a common edge case that trips up an otherwise-correct max(left,right) formula if not handled explicitly.