Delete and Compact a Forest Stored by Parent Indices

Delete and Compact a Forest Stored by Parent Indices

You are given a forest of trees represented as a zero-indexed array parents of length n, where parents[i] indicates the parent node of node i.

In this representation:

• A root node points to itself: parents[i] == i.
• Every tree in the forest is valid (no cycles other than root self-loops).

You are also given an integer target representing the node to delete, and a boolean flag compact.

Deleting a node requires deleting the node itself along with all of its descendants (the entire subtree rooted at target).

Your task is to implement the deletion under two different modes:

1. Tombstoning (compact = False):

   • Retain the original array length n.
   • Set parents[i] = -1 for target and all its descendants.
   • All surviving nodes must retain their original indices and parent pointers.

2. Compacting (compact = True):

   • Completely remove target and all its descendants.
   • Preserve the relative order of surviving nodes.
   • Re-index surviving nodes sequentially from 0 to k - 1, where k is the number of survivors.
   • Rewrite all parent references to match the new indices.
   • Ensure surviving roots remain self-referential (parents[new_i] == new_i).

Function Signature

def delete_subtree(parents: list[int], target: int, compact: bool = False) -> list[int]:
    pass

Examples

Example 1:

Input: parents = [0, 0, 1, 1, 2], target = 1, compact = False
Output: [0, -1, -1, -1, -1]
Explanation:
- Node 0 is a root.
- Node 1 is a child of 0.
- Nodes 2 and 3 are children of 1.
- Node 4 is a child of 2.
The subtree rooted at node 1 contains {1, 2, 3, 4}. Tombstoning marks them as -1.

Example 2:

Input: parents = [0, 0, 2, 2, 3], target = 0, compact = True
Output: [0, 0, 1]
Explanation:
- Subtree rooted at 0 contains {0, 1}.
- Survivors are {2, 3, 4}.
- Re-indexing: old 2 -> new 0, old 3 -> new 1, old 4 -> new 2.
- Old parent pointers: 2 -> 2 (root), 3 -> 2, 4 -> 3.
- Remapped parent pointers: new 0 -> 0 (root), new 1 -> 0, new 2 -> 1.

Constraints

• 1 <= len(parents) <= 10^5
• 0 <= parents[i] < len(parents)
• 0 <= target < len(parents)
• The input represents a valid forest where every node eventually leads to a self-referential root.