Given an array of size N that represents a Tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of Binary Tree from this array representation.

Given an array of size N that represents a Tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of Binary Tree from this array representation.

The task is to complete the function create three() which takes 2 arguments(tree array and N) and returns the root node of the tree constructed.

Expected Time Complexity: O(N).

Expected Auxiliary Space: O(N).

Example:

Input:

2

7

-1 0 0 1 1 3 5

5

-1 0 0 2 2   

Output:

0 1 2 3 4 5 6

0 1 2 3 4

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int data;
    struct Node * left;
    struct Node * right;

    Node(int x) {
        data = x;
        left = right = NULL;
    }
};

void sort_and_print(vector < int > & v) {
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    v.clear();
}

void printLevelOrder(struct Node * root) {
    vector < int > v;
    queue < Node * > q;

    q.push(root);

    Node * next_row = NULL;

    while (!q.empty()) {
        Node * n = q.front();
        q.pop();

        if (n == next_row) {
            sort_and_print(v);
            next_row = NULL;
        }

        v.push_back(n - > data);

        if (n - > left) {
            q.push(n - > left);
            if (next_row == NULL) next_row = n - > left;
        }

        if (n - > right) {
            q.push(n - > right);
            if (next_row == NULL) next_row = n - > right;
        }
    }
    sort_and_print(v);
}

Node * createTree(int parent[], int n);

/* Driver program to test above function*/
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
            cin >> a[i];

        struct Node * res = createTree(a, n);

        printLevelOrder(res);
        cout << endl;
    }

    return 0;
}

// } Driver Code Ends


Node * createTree(int parent[], int n) {
    // Your code 

    Node * root;
    Node * arr[n];
    for (int i = 0; i < n; ++i)
        arr[i] = new Node(i);
    int i = 0;
    while (i < n) {
        if (parent[i] == -1)
            root = arr[i];
        else {
            Node * temp = arr[parent[i]];
            if (!temp - > left)
                temp - > left = arr[i];
            else
                temp - > right = arr[i];
        }
        ++i;
    }

    return root;
}