N-ary Tree Deletion with Children Moving Up: Height After Deletes and Fewest Deletions

You are given a rooted N-ary tree: every node can have any number of children. Deleting a node does not delete its subtree. The node is removed, and each of its children is attached to the deleted node's parent in its place, so the children move up one level. For example, deleting nodes 2 and 7 from the tree on the left gives the tree on the right: ```text 1 1 / | \ / / | \ 2 3 4 5 6 3 4 / \ \ | 5 6 7 8 | 8 ``` The longest root-to-leaf path goes from four nodes (1-2-5-8) to three (1-5-8). The round was an hour of coding in an editor that runs code, without AI tools. For Part 1 you are expected to write and run your own tests and to state the complexity. ### Clarifying Questions - How is the tree given: node objects with child lists, a map from node to children, or a parent array? Are node ids unique? - Is height counted in nodes or in edges along the longest root-to-leaf path? - Can the root be deleted? If so, what happens to its children? - Can the delete list contain duplicates, or ids that are not in the tree? ### Part 1 — Height after deleting a list of nodes Given the tree and a list of node ids to delete, return the height of the tree after all the deletions. ```hint Does the tree have to change? Think about what a deleted node contributes to the length of a root-to-leaf path once its children have moved up, and whether the answer can be read off the original tree. ``` #### What This Part Should Cover - The correct effect of deletions on path lengths, including several deleted nodes in a row on one path - One traversal without rebuilding the tree, with its time and space complexity - The root, an empty delete list, and deep trees where recursion depth matters - Tests that are written and actually run ### Part 2 — Fewest deletions to meet a height limit Now no delete list is given. Given a maximum height N, return a set of nodes to delete, as small as possible, so that the tree's height after deleting them is at most N. Return the set itself, not its size. Pseudocode was acceptable for this part. ```hint Which deletion helps more Compare deleting a node with deleting one of its descendants on the same long path. Which root-to-leaf paths does each one shorten? ``` #### Clarifying Questions for this Part - Is N measured with the same height convention as Part 1? What is the smallest N that can be met if the root stays? - If several sets of the same minimum size exist, is any one of them acceptable? #### What This Part Should Cover - A rule for choosing the set, why the result meets the limit, and why no smaller set exists - How the set is computed in one pass over the tree, and its complexity - Edge cases: N at least the current height, the smallest possible N, and a tree that is a single long path ### What a Strong Answer Covers - Settles the tree representation, height convention and root deletion before coding - A correct bottom-up computation for Part 1 that leaves the tree unchanged, with tests that run - A correct and justified minimum set for Part 2, not just a plausible heuristic - Linear time for both parts and awareness of recursion depth ### Follow-up Questions - Deletions now arrive one at a time, and the height must be reported after each. How do you avoid recomputing from scratch? - In Part 2, deleting each node now has its own cost, and the total cost must be minimized. Does your rule still work? - How does Part 2 change if the root may also be deleted, leaving a forest?