text: Majority Element | C ++ program to demonstrate insert operation in binary search tree . ; A utility function to create a new BST node ; A utility function to insert a new node with given key in BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; find the max count ; return the ( unchanged ) node pointer ; A utility function to do inorder traversal of BST ; Driver Code ; Function call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int key ; int c = 0 ; struct node * left , * right ; } ; 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 ; } 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 = max ( 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 ▁ STRNEWLINE " , 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 cout << " No ▁ majority ▁ element STRNEWLINE " ; return 0 ; }