Print characters and their frequencies in order of occurrence using Binary Tree | C ++ implementation of the above approach ; Node in the tree where data holds the character of the string and cnt holds the frequency ; Function to add a new node to the Binary Tree ; Create a new node and populate its data part , set cnt as 1 and left and right children as NULL ; Function to add a node to the Binary Tree in level order ; Use the queue data structure for level order insertion and push the root of tree to Queue ; If the character to be inserted is present , update the cnt ; If the left child is empty add a new node as the left child ; If the character is present as a left child , update the cnt and exit the loop ; Add the left child to the queue for further processing ; If the right child is empty , add a new node to the right ; If the character is present as a right child , update the cnt and exit the loop ; Add the right child to the queue for further processing ; Function to print the level order traversal of the Binary Tree ; Add the root to the queue ; If the cnt of the character is more then one , display cnt ; If the cnt of character is one , display character only ; Add the left child to the queue for further processing ; Add the right child to the queue for further processing ; Driver code ; Add individual characters to the string one by one in level order ; Print the level order of the constructed binary tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { char data ; int cnt ; node * left , * right ; } ; node * add ( char data ) { node * newnode = new node ; newnode -> data = data ; newnode -> cnt = 1 ; newnode -> left = newnode -> right = NULL ; return newnode ; } node * addinlvlorder ( node * root , char data ) { if ( root == NULL ) { return add ( data ) ; } queue < node * > Q ; Q . push ( root ) ; while ( ! Q . empty ( ) ) { node * temp = Q . front ( ) ; Q . pop ( ) ; if ( temp -> data == data ) { temp -> cnt ++ ; break ; } if ( temp -> left == NULL ) { temp -> left = add ( data ) ; break ; } else { if ( temp -> left -> data == data ) { temp -> left -> cnt ++ ; break ; } Q . push ( temp -> left ) ; } if ( temp -> right == NULL ) { temp -> right = add ( data ) ; break ; } else { if ( temp -> right -> data == data ) { temp -> right -> cnt ++ ; break ; } Q . push ( temp -> right ) ; } } return root ; } void printlvlorder ( node * root ) { queue < node * > Q ; Q . push ( root ) ; while ( ! Q . empty ( ) ) { node * temp = Q . front ( ) ; if ( temp -> cnt > 1 ) { cout << temp -> data << temp -> cnt ; } else { cout << temp -> data ; } Q . pop ( ) ; if ( temp -> left != NULL ) { Q . push ( temp -> left ) ; } if ( temp -> right != NULL ) { Q . push ( temp -> right ) ; } } } int main ( ) { string s = " geeksforgeeks " ; node * root = NULL ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) { root = addinlvlorder ( root , s [ i ] ) ; } printlvlorder ( root ) ; return 0 ; }