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? ### What a Strong Answer Covers A state that expresses the remaining retained-height budget, a correct keep/delete recurrence, a proof of optimality, reconstruction of a minimum set, and time/space analysis. ### Follow-up Questions Why can deleting a shared ancestor be better than deleting several leaves? What happens when N already exceeds the original height? Can you reduce memory if only the minimum count is requested?