Maximum Path Sum in an Indexed Binary Tree
Company: Newrelic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Maximum Path Sum in an Indexed Binary Tree
A nonempty binary tree is represented without custom node objects. values[i] is the value of node i. children[i] is [left_index, right_index], using -1 for a missing child.
~~~python
def binary_tree_max_path_sum(
values: list[int],
children: list[list[int]]
) -> int:
...
~~~
A path is a nonempty sequence of nodes connected by parent-child edges. It may start and end anywhere and does not need to pass through root node 0. A node may occur at most once. Return the largest possible sum of node values on one path.
## Tree Validity and Error Rules
- 1 <= len(values) <= 200000
- len(children) must equal len(values).
- Every child row contains exactly two integer indices.
- Each index is either -1 or in [0, n).
- Node 0 is the root, is never a child, and every other node appears exactly once as a child.
- The representation must be connected and acyclic.
- Values and indices must be integers but not booleans.
- Invalid representations raise ValueError.
- The integer output is compared exactly.
- The implementation should run in O(n) time and O(n) auxiliary space; avoid depending on Python recursion for a tree of depth n.
## Examples
~~~text
Input:
values = [-10, 9, 20, 15, 7]
children = [[1, 2], [-1, -1], [3, 4], [-1, -1], [-1, -1]]
Output: 42
Input:
values = [-3]
children = [[-1, -1]]
Output: -3
~~~
## Hints
- Distinguish the best path that can continue to a parent from the best complete path seen anywhere.
- A negative child contribution need not improve a path.
- An explicit traversal order can replace recursive postorder.
Quick Answer: Find the maximum path sum anywhere in a binary tree represented by value and child-index arrays. Validate the entire structure, handle all-negative values, distinguish extendable from complete paths, and use iterative postorder for trees with up to 200,000 nodes.
A nonempty binary tree is represented by parallel values and [left_index, right_index] arrays. Validate the indexed representation, then return the maximum sum of any nonempty parent-child path, which may start and end anywhere.
Constraints
- Node 0 is the root and every other node appears exactly once as a child.
- Missing children use -1; every other index is in range.
- The representation must be connected and acyclic.
- Values and indices are integers but not booleans.
- Use an iterative traversal for trees as deep as n.
Examples
Input: ([-3], [[-1, -1]])
Expected Output: -3
Explanation: A one-node negative tree must choose its only node.
Input: ([-10, 9, 20, 15, 7], [[1, 2], [-1, -1], [3, 4], [-1, -1], [-1, -1]])
Expected Output: 42
Explanation: The best path joins 15, 20, and 7.
Hints
- Build an explicit traversal order from root, then process it in reverse.
- For each node, compute the best downward path that can continue to its parent.
- A complete path may use the best positive contribution from both children.