Minimum Node Deletions to Bring an N-ary Tree's Height Within k

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

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

parent = [-1, 0, 0, 1, 1, 3, 2]

 0
 / \
 1 2
 / \ \
 3 4 6
 |
 5

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

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

parent = [-1, 0, 1, 2, 1, 1]

 0
 |
 1
 /|\
 2 4 5
 |
 3

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.