Construct a special tree from given preorder traversal | Utility function to create a new Binary Tree node ; A recursive function to create a Binary Tree from given pre [ ] preLN [ ] arrays . The function returns root of tree . index_ptr is used to update index values in recursive calls . index must be initially passed as 0 ; store the current value ; of index in pre [ ] Base Case : All nodes are constructed ; Allocate memory for this node and increment index for subsequent recursive calls ; If this is an internal node , construct left and right subtrees and link the subtrees ; A wrapper over constructTreeUtil ( ) ; Initialize index as 0. Value of index is used in recursion to maintain the current index in pre [ ] and preLN [ ] arrays . ; This function is used only for testing ; first recur on left child ; then print the data of node ; now recur on right child ; Driver Code
class newNode : 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 , preLN , index_ptr , n ) : NEW_LINE INDENT index = index_ptr [ 0 ] NEW_LINE if index == n : NEW_LINE INDENT return None NEW_LINE DEDENT temp = newNode ( pre [ index ] ) NEW_LINE index_ptr [ 0 ] += 1 NEW_LINE if preLN [ index ] == ' N ' : NEW_LINE INDENT temp . left = constructTreeUtil ( pre , preLN , index_ptr , n ) NEW_LINE temp . right = constructTreeUtil ( pre , preLN , index_ptr , n ) NEW_LINE DEDENT return temp NEW_LINE DEDENT def constructTree ( pre , preLN , n ) : NEW_LINE INDENT index = [ 0 ] NEW_LINE return constructTreeUtil ( pre , preLN , index , n ) NEW_LINE DEDENT def printInorder ( node ) : NEW_LINE INDENT if node == 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 root = None NEW_LINE pre = [ 10 , 30 , 20 , 5 , 15 ] NEW_LINE preLN = [ ' N ' , ' N ' , ' L ' , ' L ' , ' L ' ] NEW_LINE n = len ( pre ) NEW_LINE root = constructTree ( pre , preLN , n ) NEW_LINE print ( " Following ▁ is ▁ Inorder ▁ Traversal ▁ of " , " the ▁ Constructed ▁ Binary ▁ Tree : " ) NEW_LINE printInorder ( root ) NEW_LINE DEDENT