Delete the Fewest Tree Nodes to Meet a Height Limit

Given a rooted multiway tree and a maximum allowed height N, return a deletion set with the fewest nodes such that the final height is at most N. Deleting a node promotes its children to its parent; it does not remove its subtree. The root cannot be deleted.

Constraints & Assumptions

• Node values are unique. As a concrete practice representation, use a parent array with node IDs 0..M-1, root 0, and parent[0] equal to -1.
• Height counts retained nodes along a root-to-leaf path; the root-only height is 1. Assume N is a positive integer.
• Return the set of deleted IDs, not just its size. Any minimum-cardinality set is valid, in any order.
• Pseudocode is acceptable, as reported. Explain how the actual set is reconstructed and how the deletion/promotion semantics appear in the algorithm.

Examples

For root 0 with children 1 and 2 and N = 1, delete {1,2}.

For 0 -> 1 with node 1 having children 2 and 3 and N = 2, deleting {1} is optimal. Deleting {2,3} also meets the limit but uses two deletions instead of one.

Clarifying Questions

Does height count edges or nodes? Can the root be removed? Is deleting a node equivalent to deleting its subtree? Are multiple optimal sets acceptable?