Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree | C ++ program to construct full binary tree using its preorder traversal and preorder traversal of its mirror tree ; A Binary Tree Node ; 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 program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } void printInorder ( Node * node ) { if ( node == NULL ) return ; printInorder ( node -> left ) ; printf ( " % d ▁ " , node -> data ) ; printInorder ( node -> right ) ; } Node * constructBinaryTreeUtil ( int pre [ ] , int preM [ ] , int & preIndex , int l , int h , int size ) { if ( preIndex >= size l > h ) return NULL ; Node * root = newNode ( pre [ preIndex ] ) ; ++ ( preIndex ) ; if ( l == h ) return root ; int i ; for ( i = l ; i <= h ; ++ i ) if ( pre [ preIndex ] == preM [ i ] ) break ; if ( i <= h ) { root -> left = constructBinaryTreeUtil ( pre , preM , preIndex , i , h , size ) ; root -> right = constructBinaryTreeUtil ( pre , preM , preIndex , l + 1 , i - 1 , size ) ; } return root ; } void constructBinaryTree ( Node * root , int pre [ ] , int preMirror [ ] , int size ) { int preIndex = 0 ; int preMIndex = 0 ; root = constructBinaryTreeUtil ( pre , preMirror , preIndex , 0 , size - 1 , size ) ; printInorder ( root ) ; } int main ( ) { int preOrder [ ] = { 1 , 2 , 4 , 5 , 3 , 6 , 7 } ; int preOrderMirror [ ] = { 1 , 3 , 7 , 6 , 2 , 5 , 4 } ; int size = sizeof ( preOrder ) / sizeof ( preOrder [ 0 ] ) ; Node * root = new Node ; constructBinaryTree ( root , preOrder , preOrderMirror , size ) ; return 0 ; }