FastPrepMaximum Nonadjacent Sum in a General Tree
Problems/Maximum Nonadjacent Sum in a General Tree

Maximum Nonadjacent Sum in a General Tree

Zip logoZip● MediumFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: Two Zip phone-screen reports describe the weighted tree choice and identify it as a general-tree form of House Robber III. The indexed parent-array input, nonnegative values, and single-root scope are explicit practice assumptions; one report mentions a disconnected-tree follow-up without a fully specified scoring rule.

Each node in a rooted tree has a nonnegative value. Choose any set of nodes with the largest possible total value, subject to one rule: a chosen node and its direct child cannot both be chosen. The tree can have any number of children per node.

The input nodes[i] = [value, parent] describes node i. Node 0 is the root and has parent -1. For every other node, its parent appears earlier in the array. Return the maximum total. Choosing no nodes is allowed.

Function

maxTreeSum(nodes: int[][]) → int

Examples

Example 1

nodes = [[5,-1],[4,0],[6,0],[7,1],[2,1],[3,2]]return = 17

Choosing the root, both grandchildren of node 1, and the grandchild of node 2 gives 5 + 7 + 2 + 3 = 17.

Example 2

nodes = [[1,-1],[10,0],[10,0],[10,1],[10,2]]return = 21

Choosing the root and both leaf grandchildren gives 21; choosing the two children gives 20.

Constraints

  • 1 <= nodes.length <= 10000.
  • Each row contains exactly two integers: [value, parent].
  • 0 <= value <= 1000.
  • nodes[0][1] == -1; for i > 0, 0 <= nodes[i][1] < i.
  • The answer fits a signed 32-bit integer.

More Zip problems

  • Maximum Survival Time in a Graph PursuitPHONE SCREEN · Seen Sep 2026
  • Find All Zip Rummy MeldsPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2026
  • Shortest Path Around Moving ParadesPHONE SCREEN · Seen Mar 2026
All Zip interview questionsSee Zip hiring insights
Saved
class Solution {
    public int maxTreeSum(int[][] nodes) {
        // Write your code here.
    }
}
Checking account…