Which data structure satisfies given requirements?

Question

Shiva is designing a new software. He wants to select a data structure to store integers such that "Deletion of the smallest element" and " Insertion of an element if it is not already present" should be done in O(log n ) time.

He made two choices.

1. Max Tree

2. Binary search tree

Which choice will satisfy all this requirements?

A. 1

B. 2

C. 1 or 2 can be used.

D. neither 1 nor 2

Comments

D is the ans?

---

Yes D is the answer :)

Answer 1

Our requirements Deletion of the smallest element 

1.using max heap:

as   it is max heap then smallest element may be present at leaf and leaf nodes can be n/2 if n is the total no of nodes.

Then worst case will be O(n) to find smallest element in max heap

2. Using binary search tree:  

In BST left node is less than or equal to root .. So smallest element must be present on left side . 

traverse the node from root to left recursively until left is NULL. The node whose left is NULL is the node with minimum value .

Worst case when bst is left skewed t: O(n)

acc to me ans should be d because none of the datastructure satisfy our first condition