Majority Element using Binary Search Tree
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 the count of a node becomes more than n/2 then return.
Illustration:
Follow the steps below to solve the given problem:
- Create a binary search tree, if the same element is entered in the binary search tree the frequency of the node is increased.
- traverse the array and insert the element in the binary search tree.
- If the maximum frequency of any node is greater than half the size of the array, then perform an inorder traversal and find the node with a frequency greater than half
- Else print No majority Element.
Below is the implementation of the above idea:
// C++ program to demonstrate insert operation in binary
// search tree.
#include <bits/stdc++.h>
using namespace std;
struct node {
int key;
int c = 0;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->c = 1;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to insert a new node with given key in
// BST
struct node* insert(struct node* node, int key, int& ma)
{
// If the tree is empty, return a new node
if (node == NULL) {
if (ma == 0)
ma = 1;
return newNode(key);
}
// Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left, key, ma);
else if (key > node->key)
node->right = insert(node->right, key, ma);
else
node->c++;
// find the max count
ma = max(ma, node->c);
// return the (unchanged) node pointer
return node;
}
// A utility function to do inorder traversal of BST
void inorder(struct node* root, int s)
{
if (root != NULL) {
inorder(root->left, s);
if (root->c > (s / 2))
printf("%d \n", root->key);
inorder(root->right, s);
}
}
// Driver Code
int main()
{
int a[] = { 1, 3, 3, 3, 2 };
int size = (sizeof(a)) / sizeof(a[0]);
struct node* root = NULL;
int ma = 0;
for (int i = 0; i < size; i++) {
root = insert(root, a[i], ma);
}
// Function call
if (ma > (size / 2))
inorder(root, size);
else
cout << "No majority element\n";
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
int c;
struct node* left;
struct node* right;
};
struct node* newNode(int item) {
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->c = 1;
temp->left = NULL;
temp->right = NULL;
return temp;
}
struct node* insert(struct node* node, int key, int* ma) {
if (node == NULL) {
if (*ma == 0)
*ma = 1;
return newNode(key);
}
if (key < node->key)
node->left = insert(node->left, key, ma);
else if (key > node->key)
node->right = insert(node->right, key, ma);
else
node->c++;
*ma = (*ma > node->c) ? *ma : node->c;
return node;
}
void inorder(struct node* root, int s) {
if (root != NULL) {
inorder(root->left, s);
if (root->c > (s / 2))
printf("%d \n", root->key);
inorder(root->right, s);
}
}
int main() {
int a[] = { 1, 3, 3, 3, 2 };
int size = sizeof(a) / sizeof(a[0]);
struct node* root = NULL;
int ma = 0;
for (int i = 0; i < size; i++) {
root = insert(root, a[i], &ma);
}
if (ma > (size / 2))
inorder(root, size);
else
printf("No majority element\n");
return 0;
}
// This code is contributed by Vaibhav Saroj.
// Java program to demonstrate insert
// operation in binary search tree.
import java.io.*;
class Node
{
int key;
int c = 0;
Node left,right;
}
class GFG{
static int ma = 0;
// A utility function to create a
// new BST node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.c = 1;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a new node
// with given key in BST
static Node insert(Node node, int key)
{
// If the tree is empty,
// return a new node
if (node == null)
{
if (ma == 0)
ma = 1;
return newNode(key);
}
// Otherwise, recur down the tree
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
node.c++;
// Find the max count
ma = Math.max(ma, node.c);
// Return the (unchanged) node pointer
return node;
}
// A utility function to do inorder
// traversal of BST
static void inorder(Node root, int s)
{
if (root != null)
{
inorder(root.left, s);
if (root.c > (s / 2))
System.out.println(root.key + "\n");
inorder(root.right, s);
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 3, 3, 3, 2 };
int size = a.length;
Node root = null;
for(int i = 0; i < size; i++)
{
root = insert(root, a[i]);
}
// Function call
if (ma > (size / 2))
inorder(root, size);
else
System.out.println("No majority element\n");
}
}
// This code is contributed by avanitrachhadiya2155
# Python3 program to demonstrate insert operation in binary
# search tree.
# class for creating node
class Node():
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.count = 1 # count of number of times data is inserted in tree
# class for binary search tree
# it initialises tree with None root
# insert function inserts node as per BST rule
# and also checks for majority element
# if no majority element is found yet, it returns None
class BST():
def __init__(self):
self.root = None
def insert(self, data, n):
out = None
if (self.root == None):
self.root = Node(data)
else:
out = self.insertNode(self.root, data, n)
return out
def insertNode(self, currentNode, data, n):
if (currentNode.data == data):
currentNode.count += 1
if (currentNode.count > n//2):
return currentNode.data
else:
return None
elif (currentNode.data < data):
if (currentNode.right):
self.insertNode(currentNode.right, data, n)
else:
currentNode.right = Node(data)
elif (currentNode.data > data):
if (currentNode.left):
self.insertNode(currentNode.left, data, n)
else:
currentNode.left = Node(data)
# Driver code
# declaring an array
arr = [3, 2, 3]
n = len(arr)
# declaring None tree
tree = BST()
flag = 0
for i in range(n):
out = tree.insert(arr[i], n)
if (out != None):
print(arr[i])
flag = 1
break
if (flag == 0):
print("No Majority Element")
// C# program to demonstrate insert
// operation in binary search tree.
using System;
public class Node
{
public int key;
public int c = 0;
public Node left,right;
}
class GFG{
static int ma = 0;
// A utility function to create a
// new BST node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.c = 1;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a new node
// with given key in BST
static Node insert(Node node, int key)
{
// If the tree is empty,
// return a new node
if (node == null)
{
if (ma == 0)
ma = 1;
return newNode(key);
}
// Otherwise, recur down the tree
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
node.c++;
// Find the max count
ma = Math.Max(ma, node.c);
// Return the (unchanged) node pointer
return node;
}
// A utility function to do inorder
// traversal of BST
static void inorder(Node root, int s)
{
if (root != null)
{
inorder(root.left, s);
if (root.c > (s / 2))
Console.WriteLine(root.key + "\n");
inorder(root.right, s);
}
}
// Driver Code
static public void Main()
{
int[] a = { 1, 3, 3, 3, 2 };
int size = a.Length;
Node root = null;
for(int i = 0; i < size; i++)
{
root = insert(root, a[i]);
}
// Function call
if (ma > (size / 2))
inorder(root, size);
else
Console.WriteLine("No majority element\n");
}
}
// This code is contributed by rag2127
<script>
// javascript program to demonstrate insert
// operation in binary search tree.
class Node {
constructor(){
this.key = 0;
this.c = 0;
this.left = null,
this.right = null;
}
}
var ma = 0;
// A utility function to create a
// new BST node
function newNode(item)
{
var temp = new Node();
temp.key = item;
temp.c = 1;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a new node
// with given key in BST
function insert(node , key) {
// If the tree is empty,
// return a new node
if (node == null) {
if (ma == 0)
ma = 1;
return newNode(key);
}
// Otherwise, recur down the tree
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
node.c++;
// Find the max count
ma = Math.max(ma, node.c);
// Return the (unchanged) node pointer
return node;
}
// A utility function to do inorder
// traversal of BST
function inorder(root , s) {
if (root != null) {
inorder(root.left, s);
if (root.c > (s / 2))
document.write(root.key + "\n");
inorder(root.right, s);
}
}
// Driver Code
var a = [ 1, 3, 3, 3, 2 ];
var size = a.length;
var root = null;
for (i = 0; i < size; i++) {
root = insert(root, a[i]);
}
// Function call
if (ma > (size / 2))
inorder(root, size);
else
document.write("No majority element\n");
// This code is contributed by gauravrajput1
</script>
Time Complexity: If a Binary Search Tree is used then time complexity will be O(n²). If a self-balancing-binary-search tree is used then it will be O(nlogn)
Auxiliary Space: O(n), As extra space is needed to store the array in the tree.
Majority Element
Find the majority element in the array. A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Examples :
Input : A[]={3, 4, 2, 4, 2, 4, 4}
Output : 4
Explanation: The frequency of 4 is greater than the half of the size of the array size.Input : A[] = {3, 3, 4, 2, 4, 4, 2, 4}
Output : No Majority Element
Explanation: There is no element whose frequency is greater than the half of the size of the array size.