Find Maximum Path Sum in N-ary Tree
Company: Nuro
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given the root of an N-ary tree. Each node contains an integer value and a list of zero or more children.
A path is a sequence of nodes where each adjacent pair is connected by an edge. The path may start and end at any two nodes in the tree, but it must not visit any node more than once.
Return the maximum possible sum of node values along any path in the tree.
Example:
```text
1
/ | \
2 3 4
/ \
5 -6
```
One maximum-sum path is `5 -> 3 -> 1 -> 4`, with sum `13`.
Constraints:
- The tree contains at least one node.
- Node values may be positive, zero, or negative.
- Each node may have any number of children.
Quick Answer: This question evaluates understanding of tree traversal and aggregation techniques, including handling of variable-arity nodes, negative values, and path-based dynamic programming on N-ary trees.
Return the maximum sum over any simple path in an N-ary tree encoded as [value, children].
Constraints
- Tree is non-empty
Examples
Input: ([1, [[2, []], [3, [[5, []], [-6, []]]], [4, []]]],)
Expected Output: 13
Explanation: Prompt-style tree.
Input: ([-5, []],)
Expected Output: -5
Explanation: Single negative node.
Input: ([0, [[-1, []], [-2, []]]],)
Expected Output: 0
Explanation: Best can be single root.
Hints
- At each node, combine the top two nonnegative child gains for a path through that node.