made easy 2019 Q33

Question

how many of the following statements is incorrect regarding the time complexity of binary search tree,AVL Tree, min heap, binary tree?

i assumed non existent elements are those which do not exists in a tree,

acc to me only (a) is incorrect!

because to find any element in BST, It takes O(n) time

Comments

Consider a BST with 2 as root and 3,4,5,6,7,8 as child ( A right skewed tree) Time complexity to find 1 will be?

---

time to search 1 will be O(1) :)

but if i have to search 9 it will take O(n) but then it will become worst case; so thats why we will not see 9 ,right.

---

Yes.

---

So, do confirm what's the correct answer.

---

according to them (d) is the only incorrect statement

---

i guess to find non existent element in min heap in best case will also take O(1) time only and in worst case , it will take O(n) time

---

searching 9 is not the best case to be considered

best case are like finding minimum element in min heap

---

yes u are right

@Tesla!

---

Ok.

So I think its clear to you also that (d) is the right answer?

---

In case of heap if the element is greater than root and less the level one elements we can find it in constant time right ?

---

yes @Hemanth_13

---

but same thing can also be applied in avl

---

​​​​​I think they are asking for the best case and not the worst case.

1. The best case will be O(1)  
   
   Eg: 3 → 4 → 5 → 6 (Right skewed). If you are trying to search for key 2 it can be done in O(1)  as the tree
   
   is right-skewed and you need not traverse the entire tree. 
    
2. As AVL is balanced time complexity will be O(log n)
    
3. In a Binary tree to find the non-existing element we have to look at every value, hence it is O(n)
    
4. In a min-heap, we will be having the smallest element at the root and if x (non-existing element) is smaller than the root element then it will take O(1)

Answer 1

Option D is incorrect.

When the element we are searching for is minimum than the root value itself then the comparision can be done in O(1) time complexity. So that is the best case

Comments

yes D is correct , in case of A take right skewed tree and an element which you have to find take less then the root element of the skewed tree than you can find that elemet is not there in O(1)

---

@indra kumar sahu Yes but in the question “incorrect” is asked so only D is the correct answer.