Google | Phone | Most frequent element in a BST
Anonymous User
6877

Given a BST with duplicates, how do you find out the most frequent value?

            50
         /          \
      40             58
   /	  \         /    \
  40      40       58     62

Most frequent element is 40.

Approaches:

  1. Do an inorder traversal and put all the nodes in an array. Then find the most frequent element in the array using a hashmap/binary search/normal iteration. Every method has its tradeoffs.
  2. Do the inorder traversal using a bst iterator and maintain a running count and update overall max count as and when we get a new element. Since the iterator returns elements in sorted order, it is same as going over iterating over an array and maintain local count and overall max count. Time Complexity - O(n), Space is O(h), h being the height of the tree.

There was a bug in the second approach which I didn't catch during the interview and realized it after the interview. Will it be held against me? The interviewer didn't point out that there was a bug in the code.

[Update] - Cleared the screening. Going for onsites.

Comments (14)