@sagar, A self-balancing balancing binary search tree(Its *BST not BT )* containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a BST, we can easily find out minimum element in O(nlogn). please note that if it would have been simple BST not Balnced BST then our complexity to lookup will changes to O(n) in worst case when tree is skewed but as question say balanced BST (check out AVL/RB Tree) they gureentte that look-up will O(logn) only why its true & will work you need to go through tree rotation (thats used to make tree balanced & reduce height ).
Since Heap is a balanced binary tree (or almost complete binary tree but not balanced BST ), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapify<http://www.cs.virginia.edu/%7Eluebke/cs332.fall00/lecture4/index.htm>(after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present because of this constraint we can't use min-heap as well . For a heap, we cannot find out in O(logn) if an element is present or not as its balanced Binary Tree(BT) , we have to search all the elements e.g.in both left & right sub-tree up-to leaf so in worst case it will take O(n) time to search an element weather ist present or not , then its present leave it else insert as a last node & call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) =O(n) search+heapify =O(search) so why correct answer is only Balanced Binary Search Tree Do Notify me if i missed something or wants more clarification ? *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/65k0xGJY6ZoJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
