Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
yes.. if the tree is not balanced it will result into O(n) search times. one can use AVL or Red black tree for this purpose.
Stl::map itself used red black tree since its balanced and red black tree has advantage over AVL here is that the rotation operation to balance the tree is O(1) whereas in AVL it could be O(logn)
I believe the answer is to make sure the BST is balanced ( or go with a self balancing BST to start with)
- R.Alam February 15, 2013