Refactor a Correct but Quadratic C++ Routine Under a Microsecond Budget

Problem Statement

You are given a list of tree nodes representing a distributed execution tree. Each node is represented as a tuple (node_id, parent_id, weight):

• node_id: A unique 32-bit signed integer identifier.
• parent_id: The node_id of the node's parent, or -1 if this node is the root.
• weight: A 32-bit signed integer representing the processing cost of this node.

In the legacy production system, a naive routine traversed upwards from every leaf using linear scans (std::find_if) across an unsorted vector to verify parents, find the root, and compute path metrics. This caused O(N^2) runtime and unacceptable latency spikes.

Refactor this routine into an optimal linear-time O(N) solution that:

1. Identifies the root_id of the tree.
2. Computes the maximum weight path from the root to any leaf node (sum of node weights inclusive of root and leaf).
3. Computes the maximum tree depth (number of edges from the root to the deepest leaf).

Your solution must execute within a strict latency budget, avoiding redundant allocations and excessive pointer chasing.

Function Signature

def analyze_execution_tree(nodes: list[tuple[int, int, int]]) -> tuple[int, int, int]:
    """
    Returns:
        (root_id, max_path_weight, max_depth)
    """
    pass

Input & Output Format

• Input: A list of tuples nodes, where each element is (node_id, parent_id, weight).
• Output: A tuple of three integers: (root_id, max_path_weight, max_depth).

Constraints

• 1 <= len(nodes) <= 100,000
• -2^31 <= node_id, parent_id <= 2^31 - 1
• -10^6 <= weight <= 10^6
• Exactly one node will have parent_id == -1.
• The input is guaranteed to form a valid, single connected tree without cycles.
• Time Complexity requirement: O(N)
• Space Complexity requirement: O(N) auxiliary space

Examples

Example 1

Input: nodes = [
    (10, -1, 5),
    (20, 10, 3),
    (30, 10, 8),
    (40, 20, 7)
]
Output: (10, 15, 2)

Explanation:

• Root is node 10 (parent_id = -1).
• Paths from root to leaves:
  • 10 -> 30: weight = 5 + 8 = 13, depth = 1 edge.
  • 10 -> 20 -> 40: weight = 5 + 3 + 7 = 15, depth = 2 edges.
• Maximum path weight is 15, maximum depth is 2.

Example 2

Input: nodes = [
    (5, -1, -10)
]
Output: (5, -10, 0)

Explanation: Single node is the root. Path weight is -10, depth is 0.