#include <iostream>

using namespace std;
const int MAX_SIZE = 100;

struct Node
{
    int key;
    Node *left, *right;
};

class ParentTree
{
private:
    int n;
    Node *root;
    int parent[MAX_SIZE];
    Node* created[MAX_SIZE];
    Node* newNode(int key);
    void createNode(int i);

public:
    ParentTree();
    Node* createTree();
    void printInorder(Node* root);
    //void enterParentArray();
    Node* getRoot();
};

ParentTree::ParentTree()
{
    cout<<"Enter length of nodes array: ";
    cin>>n;
    cout<<"Enter nodes array:"<<endl;
    for(int i = 0; i < n; i++){
        cout<<"Node on index " << i <<": ";
        cin>>parent[i];
    }
    for (int i=0; i<n; i++)
        created[i] = NULL;
}

Node* ParentTree::newNode(int key)
{
    Node *temp = new Node;
    temp->key  = key;
    temp->left  = temp->right = NULL;
    return (temp);
}

void ParentTree::createNode(int i)
{
    if (created[i] != NULL)
        return;

    created[i] = newNode(i);

    if (parent[i] == -1)
    {
        root = created[i];
        return;
    }

    if (created[parent[i]] == NULL)
        createNode(parent[i]);

    Node *p = created[parent[i]];

    if (p->left == NULL)
        p->left = created[i];
    else
        p->right = created[i];
}

Node* ParentTree:: createTree()
{
    //for (int i=0; i<n; i++)
    //    created[i] = NULL;
    //enterParentArray();
    //root = NULL;
    for (int i=0; i<n; i++)
        createNode(i);

    return root;
}

Node* ParentTree::getRoot()
{
    return root;
}

void ParentTree::printInorder(Node* root)
{
    if (root == NULL)
    {
        return;
    }
    printInorder(root->left);
    cout << root->key << " ";
    printInorder(root->right);

}


int main()
{
    ParentTree tree;
    tree.createTree();
    tree.printInorder(tree.getRoot());
    return 0;
}