Time Complexity of Binary tree and BST

Question

If an array with n-element is given then what will be the time complexity of creating Binary tree and Binary Search tree?

Answer 1

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)$. 

Comments

@rude plz put a bit more why O(n) and why O(n²)

which algo u r using here?

O(n) because just we put one time in array?

---

Even by net searching I am getting complexity of binary tree as O(logn)

---

you mean $O(nlogn)$ for Binary tree?

No. its O(n) time. @srestha

---

ok I am getting @rude

---

what getnode() function is doing here ?

---

i think binary tree should have same behavior as BST in worst case.

---

struct node * getnode(int x){
    struct node * temp = (struct node *)malloc(sizeof(struct node));
    temp->data = x;
    temp->Left = temp->Right = NULL:
    return temp;
}

@ManojK

Dude there is no worst case in Binary tree. :P 

---

See my logic is if binary tree is balanced it can be done in O(nlogn) time i.e.n time insertion in balanced tree.

If it is not balanced i.e.like BST then in worst case it will take O(n² ) time.

It may have another alternative like hash map which may be optimal .But is your code providing same functionality.?

---

The only way to get time O(N) using hash map

http://stackoverflow.com/questions/9659394/time-complexity-of-creating-a-binary-tree

i want to know are you providing the same functionality ?

---

@Manoj I think he is taking sorted sequence  and as he took dynamic memory allocation , so each node insertion by his code taking O(1) time

So, for n nodes it will be O(n)

---

and here left and right two pointer , So, is it visiting each time from root?

@Arjun sir will u see it?

---

@srestha and @ManojK 

Dude you guys are the smartest guy i know at this site. I can not believe you can not understand that whats happening. 

Dude Do not confuse Binary Search Tree with Binary tree.

 And If i have choosen the answer then I know what i have written. 

---

@rude sir Nobody is  confused with BST and Binary tree.

I know the fact behind both .

10 20 30

Simply binary tree will be look like

  10

/       \

20    30

i will simply do n time insertion which will take O(nlogn) time.

But according to your algo

   20

/      \

10     30

 

Is it conventional to think like this ?

---

first of all if you have key 10,20,30 then its not important you should have only tree like this

          10

         /    \

      20     30

It can be anything, like 

          10

         /

       20

      /

   30

 Or

10

     \

       20

           \

             30

Or

      10

          \

            20

         /

      30

Is not it? Sir in the binary tree, the only thing which is important is that we should have each node should have at most 2 children. Thats it. Structure is not important at all. 

 

Second. I have given the algorithm which have T(n) = 2T(n/2) + 1, solve this reccurance and you will get the solution. Dude. :( :( 

---

@Sir i know this conclusion choosing the middle as root and divide into sub parts will give optimal solution rt ?

---

Sir, I think it will make best Binary tree possible.

---

ok @rude I was just asking for remove my confusion as no where confirmed I find . yes u r right. it is possible in O(n) time thanks @rude @Manoj :)

---

but this is best case...in worst case it can be o(n^2)..ryt?

@srestha plz explain

---

@rude you only talked about what happehs if the array is sorted .and you derived the complexity what if array elements are not sorted. ? then what will be the time complexity in both case's. can you explain that.

---

IF ELEMENTS ARE not sorted then we will sort it in O(nogn) time after that we will apply divide and conquer

u can see: https://gateoverflow.in/74555/bst-creation