C++ Programming Code Examples C++ > Sorting Searching Code Examples Find the Number of occurrences of a given Number using Binary Search approach Find the Number of occurrences of a given Number using Binary Search approach - Implement binary search tree to find the number of occurrences of a given number. - The worst case time complexity of Binary search is O(n) but for the average case, it is O(log(n)). - Construct binary search tree for the given unsorted data array and maintain an additional count variable. - If any element is repeated then increase the count of that node. - Proceed with the search by comparing an element to the data of the node and print the count of that particular data element. - Exit. #include<iostream> using namespace std; // A structure representing a node of a tree. struct node { int data; int count; node *left; node *right; }; // A function creating a new node of the tree and assigning the data. node* CreateNode(int data) { node *newnode = new node; newnode->data = data; newnode->count = 1; newnode->left = NULL; newnode->right = NULL; return newnode; } // A function creating binary search tree. node* InsertIntoTree(node* root, int data) { // Create node using data from argument list. node *temp = CreateNode(data); node *t = new node; t = root; // If root is null, assign it to the node created. if(root == NULL) root = temp; else { // Find the position for the new node to be inserted. while(t != NULL) { // If the new data is already there then just increase the counter. if(t->data == data) { t->count++; break; } else if(t->data < data ) { if(t->right == NULL) { // If current node is NULL then insert the node. t->right = temp; break; } // Shift pointer to the left. t = t->right; } else if(t->data > data) { if(t->left == NULL) { // If current node is NULL then insert the node. t->left = temp; break; } // Shift pointer to the left. t = t->left; } } } return root; } // A function to search item in a BST. void Search(node *root, int data) { node *temp = new node; temp = root; // Run the loop until temp points to a NULL pointer or data element is found. while(temp != NULL) { if(temp->data == data) { cout<<"\nData item "<<data<<" is present "<<temp->count<<" number of times."; return; } // Shift pointer to left child. else if(temp->data > data) temp = temp->left; // Shift pointer to right child. else temp = temp->right; } cout<<"\n Data not found"; return; } int main() { char ch; int n, i, a[25] = {24, 17, 83, 8, 46, 37, 26, 92, 47, 43, 32, 26, 28, 17, 73, 28, 43, 22, 88, 43, 93, 81, 77, 23, 97}; node *root = new node; root = NULL; // Construct the BST. for(i = 0; i < 25; i++) root = InsertIntoTree(root, a[i]); up: cout<<"\nEnter the Element to be searched: "; cin>>n; Search(root, n); // Ask user to enter choice for further searching. cout<<"\n\n\tDo you want to search more...enter choice(y/n)?"; cin>>ch; if(ch == 'y' || ch == 'Y') goto up; return 0; }