Maximum Path Sum in an Indexed Binary Tree

Problem Statement

You are given a binary tree where each node is identified by an index 0 to n-1. Instead of a standard pointer-based structure, the tree is provided as two arrays: values (where values[i] is the integer weight of node i) and children (where children[i] is a pair [left_index, right_index], or -1 if the child does not exist).

Your task is to find the maximum path sum in this tree. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to pass through the root.

Function Signature

def max_path_sum(values, children):
    # children is a list of lists: [[left, right], ...]
    pass

Constraints

• n (number of nodes) is up to 200,000.
• Node weights are between -1,000 and 1,000.
• You should implement an iterative approach to avoid stack overflow errors.

Examples

Example 1:

• values = [1, 2, 3], children = [[1, 2], [-1, -1], [-1, -1]]
• The paths are: [1], [2], [3], [1, 2], [1, 3], [2, 1, 3].
• Max path sum is 6 (2 + 1 + 3).

Example 2:

• values = [-10, -5, -20], children = [[1, 2], [-1, -1], [-1, -1]]
• Max path sum is -5.

Edge Cases

• Single node trees.
• Trees with only negative values.
• Skewed trees (linked list style).