IIIT PGEE 2019

Question

What is the time complexity for insertion in binary tree in worst case?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n log n)

Comments

In the Worst case, it may grow left skew binary tree or right skew binary tree.

So, time complexity will be $O(n)$

Answer 1

 

For inserting element as the left child of D(either in a left-skewed binary tree or right skewed binary tree), we have to traverse all elements(i.e. A, B, C, D). Therefore, insertion in the binary tree has worst-case complexity of O(n).

Answer 2

Worst case scenario when binary tree is skewed therefore O(n).

Answer 3

In the worst case tree will be skewed therefore complexity will be O(n)

Answer 4

Either the tree is left skewed or right skewed that's why O(n) is correct option