Construct Binary Tree from Parent Array Representation

Given an array parent which represents a binary tree, the parent-child relationship is defined by (PARENT[i], i), meaning that the parent of i is PARENT[i]. The root node's value will be i if -1 is present at PARENT[i].

Example:

Input:

parent = {1, -1, 1}

Output:

1 0 2

Explanation:

As, parent of 0 is PARENT[0] i.e. 1. 1 is the root as PARENT[1] = -1. Parent of 2 is PARENT[2] i.e. 1.

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 3000
• Time limit: 1 sec.

Note:

From the parent array, multiple binary trees may be possible. You have to create a binary tree in such a way that these conditions satisfy:

• If the node has a left child as well as a right child, ensure the left child is smaller than the right child.
• If the node has only one child, it should be the left child.

Example Input:

parent = {1, -1, 1}

Example Output:

1 0 2

Input:

2
3
1 -1 1
3
1 2 -1

Output:

1 0 2
2 1 0