Best Root-to-Leaf Sum

core

A binary tree is given here without pointers: nodes are numbered 0 through n-1, left[u] and right[u] hold the index of u's left and right child or -1 when that child is absent, val[u] holds the node's value (values may be negative), and root is the index of the root. Every problem on this site that takes a binary tree uses that same four-part shape, so it is worth reading once: -1 is null, a node with left[u] == -1 && right[u] == -1 is a leaf, and the input is always a well-formed tree with at least one node, so root is always a valid index.

Implement max_root_to_leaf(left, right, val, root) returning the largest sum of val along any path that starts at root and ends at a leaf, counting both endpoints. Recurse down and let each call return its own subtree's answer up to its parent. The base case is what people get wrong: a missing child is not a path of sum 0, it is no path at all, so a node with exactly one child must take that child's answer rather than the better of the child and nothing. Treating -1 as a 0 looks harmless until a subtree sums to a negative number, at which point the imaginary empty path wins.

Example: with val = {1, -10, 2, 5, -100}, left = {1, 3, -1, -1, -1}, right = {2, -1, 4, -1, -1} and root = 0, max_root_to_leaf returns -4. The two root-to-leaf paths are 0 -> 1 -> 3 summing to 1 - 10 + 5 = -4 and 0 -> 2 -> 4 summing to 1 + 2 - 100 = -97; node 1 has only a left child, so its answer is forced to -10 + 5, not max(-10 + 5, -10).

Input format: each test in tests/*.in is laid out as:

Line 1: n, the number of nodes; nodes are numbered 0 to n - 1.
Line 2: the n node values.
Line 3: the n entries of left, where the i-th is the index of node i's left child, or -1 for none.
Line 4: the n entries of right, same convention.
Line 5: root, the index of the root node.

Test 03.in reads:

2
5 -3
1 -1
-1 -1
0

This is 2 nodes rooted at 0: node 0 (value 5) has node 1 (value -3) as its left child and no right child, and node 1 is a leaf.

Where you'll use it:

✦ Solution & editorial unlock with the pass.