Construct a Perfect Binary Tree from Preorder Traversal | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; Node ( int val ) { data = val ; left = right = NULL ; } } ; Node * getNewNode ( int val ) { Node * newNode = new Node ( val ) ; newNode -> data = val ; newNode -> left = newNode -> right = NULL ; return newNode ; } Node * buildPerfectBT_helper ( int preStart , int preEnd , int pre [ ] ) { if ( preStart > preEnd ) return NULL ; Node * root = getNewNode ( pre [ preStart ] ) ; ; if ( preStart == preEnd ) return root ; int leftPreStart = preStart + 1 ; int rightPreStart = leftPreStart + ( preEnd - leftPreStart + 1 ) / 2 ; int leftPreEnd = rightPreStart - 1 ; int rightPreEnd = preEnd ; root -> left = buildPerfectBT_helper ( leftPreStart , leftPreEnd , pre ) ; root -> right = buildPerfectBT_helper ( rightPreStart , rightPreEnd , pre ) ; return root ; } Node * buildPerfectBT ( int pre [ ] , int size ) { return buildPerfectBT_helper ( 0 , size - 1 , pre ) ; } void printInorder ( Node * root ) { if ( ! root ) return ; printInorder ( root -> left ) ; cout << root -> data << " ▁ " ; printInorder ( root -> right ) ; } int main ( ) { int pre [ ] = { 1 , 2 , 4 , 5 , 3 , 6 , 7 } ; int N = sizeof ( pre ) / sizeof ( pre [ 0 ] ) ; Node * root = buildPerfectBT ( pre , N ) ; cout << " Inorder traversal of the tree : " ; printInorder ( root ) ; return 0 ; }