Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree | Utility function to create a new tree node ; A utility function to print inorder traversal of a Binary Tree ; A recursive function to construct Full binary tree from pre [ ] and preM [ ] . preIndex is used to keep track of index in pre [ ] . l is low index and h is high index for the current subarray in preM [ ] ; Base case ; The first node in preorder traversal is root . So take the node at preIndex from preorder and make it root , and increment preIndex ; If the current subarry has only one element , no need to recur ; Search the next element of pre [ ] in preM [ ] ; construct left and right subtrees recursively ; return root ; function to construct full binary tree using its preorder traversal and preorder traversal of its mirror tree ; Driver code
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def prInorder ( node ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return NEW_LINE DEDENT prInorder ( node . left ) NEW_LINE print ( node . data , end = " ▁ " ) NEW_LINE prInorder ( node . right ) NEW_LINE DEDENT def constructBinaryTreeUtil ( pre , preM , preIndex , l , h , size ) : NEW_LINE INDENT if ( preIndex >= size or l > h ) : NEW_LINE INDENT return None , preIndex NEW_LINE DEDENT root = newNode ( pre [ preIndex ] ) NEW_LINE preIndex += 1 NEW_LINE if ( l == h ) : NEW_LINE INDENT return root , preIndex NEW_LINE DEDENT i = 0 NEW_LINE for i in range ( l , h + 1 ) : NEW_LINE INDENT if ( pre [ preIndex ] == preM [ i ] ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( i <= h ) : NEW_LINE INDENT root . left , preIndex = constructBinaryTreeUtil ( pre , preM , preIndex , i , h , size ) NEW_LINE root . right , preIndex = constructBinaryTreeUtil ( pre , preM , preIndex , l + 1 , i - 1 , size ) NEW_LINE DEDENT return root , preIndex NEW_LINE DEDENT def constructBinaryTree ( root , pre , preMirror , size ) : NEW_LINE INDENT preIndex = 0 NEW_LINE preMIndex = 0 NEW_LINE root , x = constructBinaryTreeUtil ( pre , preMirror , preIndex , 0 , size - 1 , size ) NEW_LINE prInorder ( root ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT preOrder = [ 1 , 2 , 4 , 5 , 3 , 6 , 7 ] NEW_LINE preOrderMirror = [ 1 , 3 , 7 , 6 , 2 , 5 , 4 ] NEW_LINE size = 7 NEW_LINE root = newNode ( 0 ) NEW_LINE constructBinaryTree ( root , preOrder , preOrderMirror , size ) NEW_LINE DEDENT