Coding questions · Nuro
Find Maximum Path Sum in N-ary Tree
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.
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:
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.
Maximum Path Sum in an N-ary Tree
Return the maximum sum over any simple path in an N-ary tree encoded as [value, children].
Hints
- At each node, combine the top two nonnegative child gains for a path through that node.