Binary Search tree (BST)
Is suppose data element are in sorted order then it will create skew tree in Binary search tree. Hence Time complexity will be $O(n^2)$.
Worst case of BST creation arrives when you get data in sorted order, and data is coming one by one. Let consider input data is 3,4,6,7,9,10,11,12,14 then, by using insertion method this tree will get created.
So this will take $O(n^2)$ times.
Binary Tree
But in Binary tree, we can choose middle elment as root and divide rest of the element as left child and right child. In this way we can achieve Binary tree creation in $O(n)$ time. Basically in the case of Binary tree you do not have to think which vakue is going where.
//Provedure to create Binary tree in O(n) time
struct node * CBT(int A[], int lb, int ub,){
if(lb<=ub){
if(lb==ub){
struct node * temp = getNode(A[lb]);
return temp;
}
else {
int mid = (lb + ub)/2;
struct node * temp = getNode(A[mid]);
temp -> left = CBT(A, lb, mid-1);
temp -> right = CBT(A, mid+1, ub);
return temp;
}
}
}
Sove this reccurance to get time complexity of $O(n)$.
