Construct a Perfect Binary Tree from Preorder Traversal | Structure of the tree ; Function to create a new node with the value val ; Return the newly created node ; Function to create the Perfect Binary Tree ; If preStart > preEnd return NULL ; Initialize root as pre [ preStart ] ; If the only node is left , then return node ; Parameters for further recursion ; Recursive Call to build the subtree of root node ; Return the created root ; Function to build Perfect Binary Tree ; Function to print the Inorder of the given Tree ; Base Case ; Left Recursive Call ; Print the data ; Right Recursive Call ; Driver Code ; Function Call ; Print Inorder Traversal
class Node : NEW_LINE INDENT def __init__ ( self , val ) : NEW_LINE INDENT self . data = val NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def getNewNode ( val ) : NEW_LINE INDENT newNode = Node ( val ) NEW_LINE return newNode NEW_LINE DEDENT def buildPerfectBT_helper ( preStart , preEnd , pre ) : NEW_LINE INDENT if ( preStart > preEnd ) : NEW_LINE INDENT return None NEW_LINE DEDENT root = getNewNode ( pre [ preStart ] ) NEW_LINE if ( preStart == preEnd ) : NEW_LINE INDENT return root NEW_LINE DEDENT leftPreStart = preStart + 1 NEW_LINE rightPreStart = leftPreStart + int ( ( preEnd - leftPreStart + 1 ) / 2 ) NEW_LINE leftPreEnd = rightPreStart - 1 NEW_LINE rightPreEnd = preEnd NEW_LINE root . left = buildPerfectBT_helper ( leftPreStart , leftPreEnd , pre ) NEW_LINE root . right = buildPerfectBT_helper ( rightPreStart , rightPreEnd , pre ) NEW_LINE return root NEW_LINE DEDENT def buildPerfectBT ( pre , size ) : NEW_LINE INDENT return buildPerfectBT_helper ( 0 , size - 1 , pre ) NEW_LINE DEDENT def printInorder ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT printInorder ( root . left ) NEW_LINE print ( root . data , " " , end = " " ) NEW_LINE printInorder ( root . right ) NEW_LINE DEDENT pre = [ 1 , 2 , 4 , 5 , 3 , 6 , 7 ] NEW_LINE N = len ( pre ) NEW_LINE root = buildPerfectBT ( pre , N ) NEW_LINE print ( " Inorder ▁ traversal ▁ of ▁ the ▁ tree : ▁ " , end = " " ) NEW_LINE printInorder ( root ) NEW_LINE