Given an array A which represents a binary tree such that the parent-child relationship is defined by (A[i], i) for every index i in the array A, build binary tree out of it. The value of root node will be i if -1 is present at index i in the array. It may be assumed that the input provided to the program is valid.

**parent[] = {-1, 0, 0, 1, 2, 2, 4, 4}**

index: 0, 1, 2, 3, 4, 5, 6, 7

– Root is represented by value -1 in the parent array which is present at index 0

– 0 is present at index 1 and 2 which represents left and right child of root.

– 1 is present at index 3 which represents left or right child of 1

– 2 is present at index 4 and 5 which represents left and right child of it.

– 4 is present at index 6 and 7 which represents left and right child of it.

The solution is very simple and effective. We create n new tree nodes each having value from 0 to n-1 where 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.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <unordered_map> using namespace std; // Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Function to perform in-order traversal of the tree void inorder(Node *root) { if (root == nullptr) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } // Function to build binary tree from given parent array 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; } // main function to build binary tree from parent array int main() { int parent[] = {-1, 0, 0, 1, 2, 2, 4, 4}; int n = sizeof parent / sizeof parent[0]; Node *root = createTree(parent, n); inorder(root); return 0; } |

The time complexity of above solution is O(n) (assuming constant time operations for `std::unordered_map`) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

how do we find no of internal nodes if we do level order traversal for this code