Construct Binary Tree from given Parent Array representation | A node structure ; 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 ; If this node is already created ; Create a new node and set created [ i ] ; If ' i ' is root , change root pointer and return ; If parent is not created , then create parent first ; Find parent pointer ; If this is first child of parent ; If second child ; Creates tree from parent [ 0. . n - 1 ] and returns root of the created tree ; Create and array created [ ] to keep track of created nodes , initialize all entries as None ; Inorder traversal of tree ; Driver Method
class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def createNode ( parent , i , created , root ) : NEW_LINE INDENT if created [ i ] is not None : NEW_LINE INDENT return NEW_LINE DEDENT created [ i ] = Node ( i ) NEW_LINE if parent [ i ] == - 1 : NEW_LINE INDENT root [ 0 ] = created [ i ] NEW_LINE return NEW_LINE DEDENT if created [ parent [ i ] ] is None : NEW_LINE INDENT createNode ( parent , parent [ i ] , created , root ) NEW_LINE DEDENT p = created [ parent [ i ] ] NEW_LINE if p . left is None : NEW_LINE INDENT p . left = created [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT p . right = created [ i ] NEW_LINE DEDENT DEDENT def createTree ( parent ) : NEW_LINE INDENT n = len ( parent ) NEW_LINE created = [ None for i in range ( n + 1 ) ] NEW_LINE root = [ None ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT createNode ( parent , i , created , root ) NEW_LINE DEDENT return root [ 0 ] NEW_LINE DEDENT def inorder ( root ) : NEW_LINE INDENT if root is not None : NEW_LINE INDENT inorder ( root . left ) NEW_LINE print root . key , NEW_LINE inorder ( root . right ) NEW_LINE DEDENT DEDENT parent = [ - 1 , 0 , 0 , 1 , 1 , 3 , 5 ] NEW_LINE root = createTree ( parent ) NEW_LINE print " Inorder ▁ Traversal ▁ of ▁ constructed ▁ tree " NEW_LINE inorder ( root ) NEW_LINE