Construct Full Binary Tree from given preorder and postorder traversals | A binary tree node has data , pointer to left child and a pointer to right child ; A recursive function to construct Full from pre [ ] and post [ ] . preIndex is used to keep track of index in pre [ ] . l is low index and h is high index for the current subarray in post [ ] ; 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 post [ ] ; Use the index of element found in postorder to divide postorder array in two parts . Left subtree and right subtree ; The main function to construct Full Binary Tree from given preorder and postorder traversals . This function mainly uses constructTreeUtil ( ) ; A utility function to print inorder traversal of a Binary Tree ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def constructTreeUtil ( pre : list , post : list , l : int , h : int , size : int ) -> Node : NEW_LINE INDENT global preIndex NEW_LINE if ( preIndex >= size or l > h ) : NEW_LINE INDENT return None NEW_LINE DEDENT root = Node ( pre [ preIndex ] ) NEW_LINE preIndex += 1 NEW_LINE if ( l == h or preIndex >= size ) : NEW_LINE INDENT return root NEW_LINE DEDENT i = l NEW_LINE while i <= h : NEW_LINE INDENT if ( pre [ preIndex ] == post [ i ] ) : NEW_LINE INDENT break NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if ( i <= h ) : NEW_LINE INDENT root . left = constructTreeUtil ( pre , post , l , i , size ) NEW_LINE root . right = constructTreeUtil ( pre , post , i + 1 , h , size ) NEW_LINE DEDENT return root NEW_LINE DEDENT def constructTree ( pre : list , post : list , size : int ) -> Node : NEW_LINE INDENT global preIndex NEW_LINE return constructTreeUtil ( pre , post , 0 , size - 1 , size ) NEW_LINE DEDENT def printInorder ( node : Node ) -> None : NEW_LINE INDENT if ( node is None ) : NEW_LINE INDENT return NEW_LINE DEDENT printInorder ( node . left ) NEW_LINE print ( node . data , end = " ▁ " ) NEW_LINE printInorder ( node . right ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT pre = [ 1 , 2 , 4 , 8 , 9 , 5 , 3 , 6 , 7 ] NEW_LINE post = [ 8 , 9 , 4 , 5 , 2 , 6 , 7 , 3 , 1 ] NEW_LINE size = len ( pre ) NEW_LINE preIndex = 0 NEW_LINE root = constructTree ( pre , post , size ) NEW_LINE print ( " Inorder ▁ traversal ▁ of ▁ " " the ▁ constructed ▁ tree : ▁ " ) NEW_LINE printInorder ( root ) NEW_LINE DEDENT