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.

Hint: Count retained nodes on original paths

Promotion changes edges, but the surviving order of nodes along an original root-to-leaf path is unchanged.

Measure Tree Height After Promoting Deleted Nodes Children

Approach

Mark deleted IDs in a boolean array, making duplicates harmless. Build adjacency lists for the original parent links, then traverse iteratively from root with retained depth one. A retained child increases that depth by one; a deleted child increases it by zero, but is still traversed so its descendants remain reachable. Promotion removes only the deleted node from each original path, preserving all surviving nodes in the same order. Thus the traversal depth equals the number of retained ancestors through that node. The maximum equals final height; deleted suffixes do not change it and the root guarantees at least one. Original adjacency lists support traversal and are not a rewritten post-deletion tree. Each node and edge is visited once and each deletion is marked once: O(n+d) time for d deleted entries, with O(n) arrays, adjacency and explicit traversal state. No recursive depth assumption is needed.

• Time complexity: O(n + len(deleted))
• Space complexity: O(n)