Minimum Node Deletions to Bring an N-ary Tree's Height Within k
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a rooted N-ary tree and a limit `k`. Deleting a node removes it from the tree, and its children are attached to its parent instead of being removed with it. Return the minimum number of nodes you must delete so that the height of the resulting tree is at most `k`.
### Function Signature
```python
def min_deletions_for_height(parent: list[int], k: int) -> int:
```
### Rules
- The tree has `n` nodes numbered `0` to `n - 1`. Node `0` is the root and `parent[0] == -1`. For every other node `i`, `parent[i]` is the index of its parent. Parents can have larger indices than their children.
- When a node is deleted, each of its children becomes a child of the deleted node's parent. If that parent is deleted too, the children keep moving up until they reach the nearest ancestor that is not deleted.
- The root can never be deleted. Any other node can be.
- The height is the number of nodes on the longest path from the root down to any node, so a tree that consists of the root alone has height 1.
- Return only the minimum count. Several different sets of nodes may achieve it.
### Constraints
- `1 <= n == len(parent) <= 10^5`
- `parent[0] == -1`, and for `i >= 1`, `0 <= parent[i] <= n - 1`; the parent links form a single tree rooted at node `0` with no cycles.
- `1 <= k <= n`, so an answer always exists: deleting every node except the root leaves height 1.
- The tree can be a single path, so its depth can reach `n`.
### Examples
**Example 1**
```text
parent = [-1, 0, 0, 1, 1, 3, 2]
0
/ \
1 2
/ \ \
3 4 6
|
5
```
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], k = 3
Output: 1
```
The height is 4 because of the path `0 → 1 → 3 → 5`. Deleting node 1 (or node 3, or node 5) leaves height 3.
**Example 2**
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], k = 2
Output: 3
```
Deleting nodes 1, 2 and 3 makes 4, 5 and 6 children of the root, giving height 2. Two deletions are not enough: the path through node 5 needs two of nodes 1, 3 and 5 removed, and the path through node 6 needs one of nodes 2 and 6 removed, and those groups share no node.
**Example 3**
```text
parent = [-1, 0, 1, 2, 1, 1]
0
|
1
/|\
2 4 5
|
3
```
```text
Input: parent = [-1, 0, 1, 2, 1, 1], k = 2
Output: 2
```
Deleting nodes 1 and 2 makes 2, 4 and 5's former positions collapse: nodes 3, 4 and 5 all become children of the root, giving height 2. Deleting the three deepest nodes instead would cost more.
Overview: Given an N-ary tree as a parent array and a limit k, find the fewest non-root nodes to delete, promoting each deleted node's children to its nearest surviving ancestor, so that the tree's height is at most k. It tests reasoning about root-to-leaf paths and choosing deletions that shorten many paths at once.
You are given a rooted N-ary tree and a limit `k`. The tree has `n` nodes numbered `0` to `n - 1`, described by the array `parent`: node `0` is the root and `parent[0] == -1`, and for every other node `i`, `parent[i]` is the index of its parent. Parents can have larger indices than their children.
Deleting a node removes it from the tree, but its children are not removed with it: each child becomes a child of the deleted node's parent. If that parent is deleted too, the children keep moving up until they reach the nearest ancestor that is not deleted. The root can never be deleted; any other node can be.
The height of a tree is the number of nodes on the longest path from the root down to any node, so a tree that consists of the root alone has height 1.
Implement `min_deletions_for_height(parent, k)`, which returns the minimum number of nodes you must delete so that the height of the resulting tree is at most `k`. Return only this minimum count; several different sets of nodes may achieve it.
### Constraints
- `1 <= n == len(parent) <= 10^5`
- `parent[0] == -1`, and for `i >= 1`, `0 <= parent[i] <= n - 1`; the parent links form a single tree rooted at node `0` with no cycles.
- `1 <= k <= n`, so an answer always exists: deleting every node except the root leaves height 1.
- The tree can be a single path, so its depth can reach `n`.
- The answer lies between `0` and `n - 1`; no value exceeds 2^31 - 1, so 32-bit integers suffice in every language.
### Example 1
```text
Input: parent = [-1, 0, 0, 1, 1, 3, 2], k = 3
Output: 1
```
```text
0
/ \
1 2
/ \ \
3 4 6
|
5
```
The height is 4 because of the path `0 → 1 → 3 → 5`. Deleting node 1 (or node 3, or node 5) leaves height 3.
### Example 2
```text
Input: parent = [-1, 0, 1, 2, 1, 1], k = 2
Output: 2
```
```text
0
|
1
/|\
2 4 5
|
3
```
Deleting nodes 1 and 2 makes nodes 3, 4 and 5 children of the root, giving height 2. Deleting the deepest nodes instead would cost more.
Constraints
- 1 <= n == len(parent) <= 10^5
- parent[0] == -1, and for i >= 1, 0 <= parent[i] <= n - 1; the parent links form a single tree rooted at node 0 with no cycles.
- 1 <= k <= n, so an answer always exists: deleting every node except the root leaves height 1.
- The tree can be a single path, so its depth can reach n.
- The answer lies between 0 and n - 1 and fits in a signed 32-bit integer.
Examples
Input: ([-1], 1)
Expected Output: 0
Explanation: Minimum tree: the root alone already has height 1 <= k, so nothing is deleted.
Input: ([-1, 0, 0, 1, 1, 3, 2], 3)
Expected Output: 1
Explanation: Example 1: height 4 via 0-1-3-5; deleting any one of nodes 1, 3 or 5 suffices (several optimal sets, one count).
Hints
- After deletions, a surviving node's depth is the number of surviving nodes on its original path from the root, so think about how many nodes each root-to-leaf path is allowed to keep.
- One deletion shortens every path that passes through the deleted node; Example 2 shows that removing nodes close to the root can be cheaper than removing deep ones.
- Parents may have larger indices than their children and the tree can be a path of 10^5 nodes, so process nodes in an order derived from the tree structure rather than by index, and avoid deep recursion.