CODEWITHSUNDEEP
c++algorithmdictionarytreebinary-search-tree
Shivam Mitra
Shivam Mitra

Reputation: 1052

Minimum/maximum element in a balanced binary search time in O(1) time

I know we can find minimum/maximum in a binary search tree in O(logn) time. But map in c++ gives us the minimum/maximum in constant time. We can find minimum element in a map using the map::begin and maximum using map::rbegin . Both these operation takes constant time. Can anyone suggest a method that makes finding minimum/maximum O(1) ?

Upvotes: 0

Views: 2089

Answers (1)

Priyansh Goel
Priyansh Goel

Reputation: 2660

C++ map is not implemented by BST. It is implemented by Red Black Tree. If you want to find min/max in BST by O(1),you can store the two pointers to the leftmost node and rightmost node in the tree. Else, you can use minheap or maxheap to find out min/max in O(1).

Upvotes: 2

Related Questions