Maximize non-adjacent sum on an N-ary tree
Company: ZipHQ
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an **N-ary tree** (each node may have 0..k children). Each node contains an integer value (can be 0 or positive).
You want to select a set of nodes such that **no selected node is directly connected to another selected node** (i.e., you cannot select both a node and any of its children). Return the **maximum possible sum** of selected node values.
### Requirements
- Implement a tree node structure yourself, e.g.:
- `value: int`
- `children: List[Node]`
- Write a function `maxNonAdjacentTreeSum(root) -> int`.
### Input / Output
- **Input:** `root` pointer/reference to the root node (or `null` for empty tree).
- **Output:** an integer representing the maximum achievable sum.
### Example
If the tree is:
- Root 3 with children 2 and 3
- Node 2 has child 3
- Node 3 (child of root) has child 1
One optimal selection is nodes with values `3 (root) + 3 (grandchild under 2) + 1 = 7`, so return `7`.
### Constraints
- Number of nodes `n` up to ~10^5.
- Aim for **O(n)** time.
- Extra space should be proportional to recursion depth or explicit stack size.
Quick Answer: This question evaluates skills in tree-based dynamic programming, recursive traversal, and per-node state management for selecting non-adjacent nodes in an N-ary tree.
Given nodes as [value, child_indices] and a root index, return the maximum sum selecting no parent-child pair together.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: ([[3,[1,2]], [2,[3]], [3,[4]], [3,[]], [1,[]]], 0)
Expected Output: 7
Explanation: Prompt shape.
Input: ([], None)
Expected Output: 0
Explanation: Empty tree.
Input: ([[5,[]]], 0)
Expected Output: 5
Explanation: Single node.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.