Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
Keep an array of 3 elements. Initialized to Integer.minimum.
Traverse the BT (inorder) and push the elements in to a position it fits in the 3 element array/linked list(sorted) and remove the last element. After the whole traversal is complete then take the last index in the array..... simple.
This way you can solve for any order - of course it taxes memory a bit.
If it is a binary search tree, you could do in-order with going to right first and then to left.
- Sunny August 31, 2017This will make in-order traverse in descending order and stop traversal at count = 3.
If this is not a binary search tree, then convert the tree to a max heap - should be O(n) I believe. then pop three times to get the third highest.