Flatten Binary Tree

You are given a binary tree represented by a parent array. Each node is assigned a unique integer value equal to its index (i.e. node i has value i). The parent array is defined as follows: for each index (i), the value (parent[i]) represents the index of its parent. If (parent[i] = -1), then node (i) is the root of the tree. For any node with parent (p), if (p)'s left child is not yet assigned, then node (i) is attached as its left child; otherwise, it is attached as the rightmost node in the chain starting from the left child.\n\nAfter building the tree, your task is to flatten it into a linked list in preorder. In other words, you need to rewire the tree so that each node's left pointer is set to null and its right pointer points to the next node in the preorder traversal. Recall that the preorder traversal is defined as: ( \text{preorder}(node) = [node] \Vert \text{preorder}(node.left) \Vert \text{preorder}(node.right) ).\n\nThe final output should be the sequence of node values from the flattened tree, printed in order separated by a single space for each test case.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. For each test case:\n\n- The first line contains an integer (N), the number of nodes in the tree.\n- The second line contains (N) space-separated integers, where the (i)-th integer represents (parent[i]) (with (parent[i] = -1) indicating that node (i) is the root).

outputFormat

For each test case, output a single line containing the values of the flattened tree's nodes in preorder (i.e. the order in which they appear in the flatten linked list), separated by a single space. The output is printed to standard output (stdout).## sample

2
5
-1 0 0 1 1
3
-1 0 1

0 1 3 4 2
0 1 2