418. Sum of Nodes on the Longest Root-to-Leaf Path

Given a binary tree, consider every root-to-leaf path and find the ones with the most nodes (the longest paths); among those tied-for-longest paths, print the largest sum of node values.

Input: A single line of space-separated level-order tokens ('N' for missing children) describing the binary tree. Output: Print a single integer - the largest node-value sum among the root-to-leaf paths tied for the most nodes.

1 <= number of nodes <= 10^5

A single-node tree's only path is just the root itself - a trivial but useful base case to keep in mind when reasoning about the recursion's correctness.

Among all root-to-leaf paths, find the ones with the MOST nodes (the longest), and among those, report the largest sum of values. Brute force: Enumerate every root-to-leaf path explicitly, storing both its length and sum, then scan all of them afterward to find the best - this works but requires storing every path's full data, when a running comparison during a single traversal suffices. Optimised: Tracking a running 'best node count' and 'best sum for that count' as a single post-order (or preorder) traversal proceeds lets you make the length-then-sum comparison decision immediately at each leaf, with no need to store or revisit any path's full data afterward.

First do a BFS or DFS pass that only tracks depth to find the maximum root-to-leaf depth as a single number, without storing any node values. Then do a second DFS pass that walks root-to-leaf paths accumulating running sums, and among leaves reached at exactly that maximum depth, keeps the largest running sum. This avoids storing full path lists, but still requires walking the tree twice. Time: O(n) Space: O(n)

Do one post-order DFS where each call returns a pair (depth of longest path in this subtree, sum along that longest path); at each node, combine the children's pairs by keeping whichever child has the greater depth (breaking ties by greater sum), then add the current node's value to that sum and increment the depth by one. This computes the depth and the corresponding best sum together in a single traversal, needing only recursion-stack space proportional to the tree's height rather than two full passes or storing every path. Time: O(n) Space: O(h) recursion stack

Traverse the tree with DFS, and at every leaf, record the complete list of node values on the path from root to that leaf. Once every path has been collected, find the maximum path length among them, then scan again over only the paths with that maximum length to pick the one with the largest sum. Storing every full path explicitly uses far more memory and time than necessary just to compare depths and sums. Time: O(n * h) where h is tree height Space: O(n * h)

1. Recurse toward every leaf, tracking BOTH the current path's node count AND its running sum of values. 2. At each leaf, compare its path's node count against the best node count found so far: a STRICTLY LONGER path always replaces the current best (regardless of its sum); a TIED-length path only replaces it if its sum is larger. 3. The final best sum, after checking every leaf, is the answer.

Time: O(n) - one single traversal, visiting every node once. Space: O(h) for the recursion stack.

Test a single-node tree (its own value is the answer), multiple leaves tied for the longest path length where the larger sum must win, and n=10^5 nodes for performance.

Be precise about the exact tie-breaking priority: LENGTH always wins first, and SUM is only the tie-breaker among equally-long paths - a common mistake is comparing sums directly without first checking length.