Majority element using BST

Question

The question has already been discussed in the link. Find the majority element in array

I know there are more optimized soln's than this but I couldn't understand the approach as discussed below. BTW it's an unsorted array.

Node of the Binary Search Tree (used in this approach) will be as follows.

 struct tree
  {
    int element;
    int count;
  }BST;

" Insert elements in BST one by one and if an element is already present then increment the count of the node. " At any stage, if count of a node becomes more than n/2 then return. The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

If we are passing element one by one to a function, how can we compare if an element is already present or not and increase the count?

Each time you call the function, you are modifying an object. So the global state is changing in each call. — Bill Lynch, Apr 12 '15 at 13:51
That structure looks pretty useless. A tree is something that consists of one element and one "count", and nothing else? — molbdnilo, Apr 12 '15 at 14:56
Hey there. I know this is a rather old question. I tried to be really precise with my answer. didn't my answer help you at all? If something is still unclear, you could comment and I would edit my answer as necessary. — dingalapadum, Oct 19 '15 at 07:21

score 0 · Answer 1 · answered Apr 12 '15 at 13:21

First of all the struct should probably have pointers to the child nodes. Something along the lines

struct node{
 int value;
 int count;
 node *leftChild;
 node *rightChild;
};

To insert an element in the BST you check whether the current node is larger or smaller or equal to the element you are trying to insert. If it is smaller, go left, if it is larger, go right, if it is equal increment the count field of this node. If you reach a null-node (child of a leave), then create a new node at this location with the value you are inserting and set the count to 1.

Finally have two variables to keep track of the majority element and the number of times it occurred and update them if necessary when inserting an element.

Assuming that the majority element indeed occurs n/2 or more of the times, you don't need the additional variables, but as noted in your quote you can simply return once you increment a nodes counter to be >=n/2. So, whenever you increment a counter, compare against n/2.

As you noted, there are far better solutions if the task really is just about knowing the majority element in the end, but I assume that you want to stick to the BST approach.

Majority element using BST

1 Answers1