Prune a Multiway Tree to a Maximum Depth

## Problem You are given a rooted multiway tree as a parent array. Node `0` is the root and `parent[i]` is the parent of node `i` for every `i > 0`. Root depth is `0`. Deleting a node removes that node and its entire subtree. Return the minimum number of explicit node deletions needed so that every remaining node has depth at most `k`. The root may not be deleted. ### Function Contract Implement `minimumSubtreeDeletionsForDepth(parent, k)` and return one integer. ### Constraints & Assumptions - `1 <= len(parent) <= 200,000`. - `parent[0] == -1` and `0 <= parent[i] < i` for `i > 0`, so the input is a valid rooted tree. - `0 <= k <= len(parent)`. - Deleting one node counts as one operation regardless of subtree size. ### Clarifying Questions to Ask - Does deleting a node promote its children? No; it removes the whole subtree. - Is root depth zero or one? Zero. - May the root be deleted when `k` is negative? No; `k` is nonnegative. ```hint Cut each over-depth branch at its first illegal node Every node at depth `k + 1` roots a disjoint subtree that must disappear. Deleting that node removes all deeper violations with one operation. ``` ### Examples ```text parent = [-1,0,0,1,1,3], k = 2 -> 1 ``` Only node `5` is deeper than two; deleting node `5` is sufficient. ```text parent = [-1,0,0,1,1,2,2], k = 1 -> 4 ``` The four depth-two nodes are roots of four disjoint over-depth subtrees. ### Evaluation Focus - Uses the stated depth convention and subtree-deletion semantics. - Counts first illegal nodes, not every deeper descendant. - Handles `k = 0`, a single-node tree, and `k` at least the existing maximum depth. - Runs in `O(n)` time and `O(n)` or `O(height)` traversal space. ### Extensions to Discuss 1. How would weighted deletion costs change the greedy argument? 2. What if deletion promoted a node's children to its parent? 3. How would you return the exact nodes to delete?