using namespace std;
template<typename T>
class Binarytree{
public:
T data;
Binarytree<T> *left;
Binarytree<T> *right;
Binarytree(T data){
this->data=data;
left=NULL;
right=NULL;
}
~Binarytree(){
if (left) delete left;
if (right) delete right;
}
};
void preorder(Binarytree<int>* root)
{
if(root==NULL)
{
return;
}
cout<<" "<<root->data;
preorder(root->left);
preorder(root->right);
}
void postorder(Binarytree<int>* root){
if(root==NULL)
return;
postorder(root->left);
postorder(root->right);
cout<<" "<<root->data;
}
Binarytree<int>* construct(int *arr,int si,int end)
{
if(si>end)
{
return NULL;
}
int mid=(si+end)/2;
Binarytree<int>* root=new Binarytree<int>(arr[mid]);
Binarytree<int>*lchild=construct(arr,si,mid-1);
Binarytree<int>* rchild=construct(arr,mid+1,end);
root->left=lchild;
root->right=rchild;
return root;
}
int main() {
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
Binarytree<int>* root=construct(arr,0,n-1);
cout<<"Pre order :";
preorder(root);
cout<<"\n";
cout<<"In order :";
for(int i=0;i<n;i++)
{
cout<<" "<<arr[i];
}cout<<"\n";
cout<<"Post order:";
postorder(root);
cout<<endl;
delete root;
cout<<endl;
return 0;
}```