Find Tree Height After Deleting Nodes and Promoting Children

Delete selected nodes from a rooted multiway tree. Deleting a node promotes all of its children to its parent; it does not delete the descendants. Return the final tree height measured in nodes along the longest root-to-leaf path.

Implement height_after_deletions(parent: int[], deleted: int[]) -> int.

Constraints & Assumptions

• The tree has 1 <= n <= 200000 nodes with unique IDs 0..n-1. Node 0 is the root, parent[0] == -1, and each other entry identifies its parent. This array is a practice representation of the source's unique node values.
• The parent array describes a valid tree but parent IDs need not be smaller than child IDs.
• Every deleted ID is a non-root node. Duplicate deleted IDs have no extra effect.
• Any number of non-root nodes may be deleted. A root-only result has height 1.
• Only the height is required; do not construct a rewritten tree merely to return it.
• Aim for O(n + len(deleted)) time. Account for traversal depth when choosing recursive or iterative code.

Examples

parent = [-1,0,0,2,2,4], deleted = [2]
result = 3

The retained path 0 -> 4 -> 5 has three nodes after node 2's children are promoted.

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

Explain why deleting an internal node reduces the contribution of that node but preserves the descendants' contribution. Include tests for the root-only tree, no deletions, consecutive deleted ancestors, and all non-root nodes deleted, and state time and space complexity.