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;
}
Comments