Construct Binary Tree from given Parent Array representation - GeeksforGeeks

Construct Binary Tree from given Parent Array representation - GeeksforGeeks
Given an array that represents a tree in such a way array indexes are values in tree nodes 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 given Binary Tree from this given representation.

Input: parent[] = {1, 5, 5, 2, 2, -1, 3}
Output: root of below tree
          5
        /  \
       1    2
      /    / \
     0    3   4
         /
        6 
Explanation: 
Index of -1 is 5.  So 5 is root.  
5 is present at indexes 1 and 2.  So 1 and 2 are
children of 5.  
1 is present at index 0, so 0 is child of 1.
2 is present at indexes 3 and 4.  So 3 and 4 are
children of 2.  
3 is present at index 6, so 6 is child of 3.

    // Creates a node with key as 'i'.  If i is root, then it changes

    // root.  If parent of i is not created, then it creates parent first

    void createNode(int parent[], int i, Node created[])

    {

        // If this node is already created

        if (created[i] != null)

            return;

  

        // Create a new node and set created[i]

        created[i] = new Node(i);

  

        // If 'i' is root, change root pointer and return

        if (parent[i] == -1)

        {

            root = created[i];

            return;

        }

  

        // If parent is not created, then create parent first

        if (created[parent[i]] == null)

            createNode(parent, parent[i], created);

  

        // Find parent pointer

        Node p = created[parent[i]];

  

        // If this is first child of parent

        if (p.left == null)

            p.left = created[i];

        else // If second child

          

            p.right = created[i];

    }

  

    /* Creates tree from parent[0..n-1] and returns root of

       the created tree */

    Node createTree(int parent[], int n)

    {   

        // Create an array created[] to keep track

        // of created nodes, initialize all entries

        // as NULL

        Node[] created = new Node[n];

        for (int i = 0; i < n; i++)

            created[i] = null;

  

        for (int i = 0; i < n; i++)

            createNode(parent, i, created);

  

        return root;

    }

http://www.techiedelight.com/build-binary-tree-given-parent-array/
We create n new tree nodes each having value from 0 to n-1where n is the size of the array and store them in a map or array for quick lookup. Then we traverse the given parent array and build the tree by setting parent-child relationship defined by (A[i], i) for every index i in the array A. As several binary trees can be constructed from one input, below solution would construct any one of them. The solution will always set left child for a node before setting its right child.

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

{

    // create an empty map

    unordered_map<int, Node*> map;

 

    // create n new tree nodes each having value from 0 to n-1

    // and store them in a map

    for (int i = 0; i < n; i++)

        map[i] = newNode(i);

 

    // represents root node of binary tree

    Node *root = nullptr;

 

    // traverse the parent array and build the tree

    for (int i = 0; i < n; i++)

    {

        // if parent is -1, set root to current node having

        // value i (stored in map[i])

        if (parent[i] == -1)

            root = map[i];

        else

        {

            // get parent node for current node

            Node *ptr = map[parent[i]];

 

            // if parent's left child is filled,

            // map the node to its right child

            if (ptr->left)

                ptr->right = map[i];

 

            // if parent's left child is empty, map the node to it

            else

                ptr->left = map[i];

        }

    }

 

    // return root of the constructed tree

    return root;

}

Read full article from Construct Binary Tree from given Parent Array representation - GeeksforGeeks