Delete a Node from a Forest Represented by Parent Index Array

Problem: Delete a Node from a Forest Represented by a Parent Index Array You are given an array parent of length n, representing a forest. Nodes are indexed from 0 to n - 1. parent[i] is the parent index of node i. If node i is a root, then parent[i] == i. The input is always valid. There are no null / None values and no invalid indices. Given a node index deleteIndex, delete that node and return the new parent array. For this version, assume: Only the node deleteIndex itself is removed; its subtree is not removed. Any node whose parent was deleteIndex becomes a new root. After deletion, the array length becomes n - 1, and node indices are compressed to 0..n-2. Parent indices of all remaining nodes must be remapped accordingly. The returned array must still satisfy the rule that every root points to itself. Input Format n parent[0] parent[1] ... parent[n-1] deleteIndex Output Format Print the resulting parent array separated by spaces. If the resulting array is empty, print an empty line. Constraints 1 <= n <= 2 * 10^5 0 <= parent[i] < n 0 <= deleteIndex < n The input always represents a valid forest. Example 1 Input: 5 0 0 1 1 3 1 Output: 0 1 2 2 Example Input 5 0 0 1 1 3 1 Output 0 1 2 2