Construct a special tree from given preorder traversal | A program to construct Binary Tree from preorder traversal ; A binary tree node structure ; 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 function to test above functions
#include <bits/stdc++.h> NEW_LINE struct node { int data ; struct node * left ; struct node * right ; } ; struct node * newNode ( int data ) { struct node * temp = new struct node ; temp -> data = data ; temp -> left = NULL ; temp -> right = NULL ; return temp ; } struct node * constructTreeUtil ( int pre [ ] , char preLN [ ] , int * index_ptr , int n ) { int index = * index_ptr ; if ( index == n ) return NULL ; struct node * temp = newNode ( pre [ index ] ) ; ( * index_ptr ) ++ ; if ( preLN [ index ] == ' N ' ) { temp -> left = constructTreeUtil ( pre , preLN , index_ptr , n ) ; temp -> right = constructTreeUtil ( pre , preLN , index_ptr , n ) ; } return temp ; } struct node * constructTree ( int pre [ ] , char preLN [ ] , int n ) { int index = 0 ; return constructTreeUtil ( pre , preLN , & index , n ) ; } void printInorder ( struct node * node ) { if ( node == NULL ) return ; printInorder ( node -> left ) ; printf ( " % d ▁ " , node -> data ) ; printInorder ( node -> right ) ; } int main ( ) { struct node * root = NULL ; int pre [ ] = { 10 , 30 , 20 , 5 , 15 } ; char preLN [ ] = { ' N ' , ' N ' , ' L ' , ' L ' , ' L ' } ; int n = sizeof ( pre ) / sizeof ( pre [ 0 ] ) ; root = constructTree ( pre , preLN , n ) ; printf ( " Following ▁ is ▁ Inorder ▁ Traversal ▁ of ▁ the ▁ Constructed ▁ Binary ▁ Tree : ▁ STRNEWLINE " ) ; printInorder ( root ) ; return 0 ; }