### C++ template based program to construct BST from given Preorder traversal

Description:
preorder traversal : Traverse the root node first then traverse left subtree and then right subtree.
eg: preorder={12,10,8,11,20,14,22}
Approach:Time complexity O(n*2)
First node of preorder always root node and all the nodes have less value than root node will be left subtree and greater nodes will be right subtree.
first element of list will be root node and list will be divided in to two parts from greater value than root node and it will happen recursively until the list is not empty.
12 is root node, list is divided by 20 because 20 is greater than 12
so, the first list after adding 12 in BST is {10,8,11} and second is {20,14,22}, It will repeated recursively.

CODE:

#include<iostream> #include<stdlib.h> using namespace std; template<class X> class tree { private: X *node_list; int size_list; int index; //structure of BST node typedef struct node { X data; node *left; node *right; }node; public: node *root=NULL;//root node of BST tree(X *list_t, int size_l) { node_list=list_t; size_list=size_l; index=0; } private: node* create_node(X data)//function to create a new node { node *temp=new node; temp->data=data; temp->left=NULL; temp->right=NULL; return temp; } private: //beg is starting index and last is end index of list node* bst(X *node_list, int present_index, int beg, int last, int size_list)//recursive function to construct BST { index=present_index; if(index>=size_list||beg>last) return NULL; node *root=create_node(*(node_list+ index)); index=index+1; //list cannot be further divided if(beg==last) return root; int i; //loop to make division of list for(i=beg;i<=last;i++) if(*(node_list+i)>root->data) break; root->left=bst(node_list,index,index,i-1,size_list); root->right=bst(node_list,index,i,last,size_list); return root; } public: node* construct_bst() { return bst(node_list,index,0,size_list-1,size_list); } //Function to print postorder traversal of construct binary tree void print_postorder(node *root) { if(root) { print_postorder(root->left); print_postorder(root->right); cout<<root->data<<" "; } } }; //Driver function int main () { int preorder[]={12,10,8,11,20,14,22}; int size_list=sizeof(preorder)/sizeof(int); tree <int>BST(preorder,size_list); BST.root=BST.construct_bst(); cout<<"Postorder traversal is: "; BST.print_postorder(BST.root); return 0; }