given the following array a 8 draw corresponding binary tree

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

For example,

Parent: [-1, 0, 0, 1, 2, 2, 4, 4]
Index : [ 0, 1, 2, 3, 4, 5, 6, 7]

Note that,

• -1 is present at index 0, which implies that the binary tree root is node 0.
• 0 is present at index 1 and 2, which implies that the left and right children of node 0 are 1 and 2.
• 1 is present at index 3, which implies that the left or the right child of node 1 is 3.
• 2 is present at index 4 and 5, which implies that the left and right children of node 2 are 4 and 5.
• 4 is present at index 6 and 7, which implies that the left and right children of node 4 are 6 and 7.

The corresponding binary tree is:

Practice this problem

The solution is simple and effective – create n new tree nodes, each having values from 0 to n-1, where n is the array's size, and store them in a map or array for the quick lookup. Then traverse the given parent array and build the tree by setting the parent-child relationship defined by (A[i], i) for every index i in array A. Since several binary trees can be formed from a single input, the solution should build any of them. The solution will always set the left child for a node before setting its right child.

The algorithm can be implemented as follows in C++, Java, and Python:

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

#include <iostream> #include <vector> #include <unordered_map> using namespace std ; // Data structure to store a binary tree node struct Node { int data ; Node * left , * right ; Node ( int data ) { this -> data = data ; this -> left = this -> right = nullptr ; } } ; // Function to perform inorder traversal on the tree void inorder ( Node * root ) { if ( root == nullptr ) { return ; } inorder ( root -> left ) ; cout << root -> data << " " ; inorder ( root -> right ) ; } // Function to build a binary tree from the given parent array Node * createTree ( vector < int > const &parent ) { int n = parent . size ( ) ; // create an empty map unordered_map < int , Node * > map ; // create `n` new tree nodes, each having a value from 0 to `n-1`, // and store them in a map for ( int i = 0 ; i < n ; i ++ ) { map [ i ] = new Node ( i ) ; } // represents the root node of a binary tree Node * root = nullptr ; // traverse the parent array and build the tree for ( int i = 0 ; i < n ; i ++ ) { // if the parent is -1, set the root to the current node having the // value `i` (stored in map[i]) if ( parent [ i ] == - 1 ) { root = map [ i ] ; } else { // get the parent for the current node Node * ptr = map [ parent [ i ] ] ; // if the parent's left child is filled, // map the node to its right child if ( ptr -> left ) { ptr -> right = map [ i ] ; } // if the parent's left child is empty, map the node to it else { ptr -> left = map [ i ] ; } } } // return root of the constructed tree return root ; } int main ( ) { vector < int > parent = { - 1 , 0 , 0 , 1 , 2 , 2 , 4 , 4 } ; Node * root = createTree ( parent ) ; inorder ( root ) ; return 0 ; }

Download  Run Code

Output:

3 1 0 6 4 7 2 5

Java

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

import java . util . HashMap ; import java . util . Map ; // A class to store a binary tree node class Node { int data ; Node left = null , right = null ; Node ( int data ) { this . data = data ; } } class Main { // Function to perform inorder traversal on the tree public static void inorder ( Node root ) { if ( root == null ) { return ; } inorder ( root . left ) ; System . out . print ( root . data + " " ) ; inorder ( root . right ) ; } // Function to build a binary tree from the given parent array public static Node createTree ( int [ ] parent ) { // create an empty map Map < Integer , Node > map = new HashMap <> ( ) ; // create `n` new tree nodes, each having a value from 0 to `n-1`, // and store them in a map for ( int i = 0 ; i < parent . length ; i ++ ) { map . put ( i , new Node ( i ) ) ; } // represents the root node of a binary tree Node root = null ; // traverse the parent array and build the tree for ( int i = 0 ; i < parent . length ; i ++ ) { // if the parent is -1, set the root to the current node having the // value `i` (stored in map[i]) if ( parent [ i ] == - 1 ) { root = map . get ( i ) ; } else { // get the parent for the current node Node ptr = map . get ( parent [ i ] ) ; // if the parent's left child is filled, map the node to its right // child if ( ptr . left != null ) { ptr . right = map . get ( i ) ; } // if the parent's left child is empty, map the node to it else { ptr . left = map . get ( i ) ; } } } // return root of the constructed tree return root ; } public static void main ( String [ ] args ) { int [ ] parent = { - 1 , 0 , 0 , 1 , 2 , 2 , 4 , 4 } ; Node root = createTree ( parent ) ; inorder ( root ) ; } }

Download  Run Code

Output:

3 1 0 6 4 7 2 5

Python

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

# A class to store a binary tree node class Node : def __init__ ( self , data , left = None , right = None ) : self . data = data self . left = left self . right = right # Function to perform inorder traversal on the tree def inorder ( root ) : if root is None : return inorder ( root . left ) print ( root . data , end = ' ' ) inorder ( root . right ) # Function to build a binary tree from the given parent list def createTree ( parent ) : # create an empty dictionary d = { } # create `n` new tree nodes, each having a value from 0 to `n-1`, # and store them in a dictionary for i in range ( len ( parent ) ) : d [ i ] = Node ( i ) # represents the root node of a binary tree root = None # traverse the parent list and build the tree for i , e in enumerate ( parent ) : # if the parent is -1, set the root to the current node having the # value `i` (stored in map[i]) if e == - 1 : root = d [ i ] else : # get the parent for the current node ptr = d [ e ] # if the parent's left child is filled, map the node to its right child if ptr . left : ptr . right = d [ i ] # if the parent's left child is empty, map the node to it else : ptr . left = d [ i ] # return root of the constructed tree return root if __name__ == '__main__' : parent = [ - 1 , 0 , 0 , 1 , 2 , 2 , 4 , 4 ] root = createTree ( parent ) inorder ( root )

Download  Run Code

Output:

3 1 0 6 4 7 2 5

The time complexity of the above solution is O(n), where n is the total number of nodes in a binary tree (assuming constant-time operations for the hash table). The auxiliary space required by the program is O(n).

joinerpaligar69.blogspot.com

Source: https://www.techiedelight.com/build-binary-tree-given-parent-array/

Share this post