Given Preorder can you make BST from it then print the sorted output from BST

#include<iostream>
#include<stdlib.h>
using namespace std;
 
typedef struct tree{
int val;
struct tree *left;
struct tree *right;
}tree;
 
tree* insert(tree* root, int val)
{
if(root == NULL)
{
tree* temp = (tree*) malloc(sizeof(tree));
temp->val = val;
temp->left = NULL;
temp->right = NULL;
return temp;
}
 
tree* node = (tree*) malloc(sizeof(tree));
if(root->val < val)
root->right = insert(root->right, val);
else
root->left = insert(root->left, val);
return root;
}
 
tree* buildBST(int preOrder[], int length)
{
tree* root;
if(length != 0)
{
root = (tree*) malloc(sizeof(tree));
root->val = preOrder[0];
root->left = NULL;
root->right = NULL;
}
else
return NULL;
 
for(int i = 1; i < length; i++)
{
root = insert(root, preOrder[i]);
}
 
return root;
}
 
void printInOrder(tree* BST)
{
if(BST == NULL) return;
printInOrder(BST->left);
cout << BST->val << " ";
printInOrder(BST->right);
}
 
void printPreOrder(tree* BST)
{
if(BST == NULL) return;
cout << BST->val << " ";
printPreOrder(BST->left);
printPreOrder(BST->right);
}
 
int main(void)
{
int preOrder[] = {10, 5, 3, 4, 6, 11, 13, 12};
tree* BST = buildBST(preOrder, sizeof(preOrder) / sizeof(int));
printInOrder(BST);
cout << endl;
printPreOrder(BST);
cout << endl;
}

 Time Complexity O(N^2) in Case of Skewed Tree
 Space Complexity O(1)
Run Here http://ideone.com/KVDrB