Print Strings In Reverse Dictionary Order Using Trie | C ++ program to print array of string in reverse dictionary order using trie ; Trie node ; endOfWord is true if the node represents end of a word ; Function will return the new node initialized NULL ; Initialize null to the all child ; Function will insert the string in a trie recursively ; Create a new node ; Recursive call for insertion of string ; Make the endOfWord true which represents the end of string ; Function call to insert a string ; Function call with necessary arguments ; Function to check whether the node is leaf or not ; Function to display the content of trie ; If node is leaf node , it indicates end of string , so a null character is added and string is displayed ; Assign a null character in temporary string ; check if NON NULL child is found add parent key to str and call the display function recursively for child node ; Function call for displaying content ; Driver code ; After inserting strings , trie will look like root / \ a t | | n h | \ | s y e | | \ w i r | | | e r e | r
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define CHILDREN  26 NEW_LINE #define MAX  100 NEW_LINE struct trie { trie * child [ CHILDREN ] ; bool endOfWord ; } ; trie * createNode ( ) { trie * temp = new trie ( ) ; temp -> endOfWord = false ; for ( int i = 0 ; i < CHILDREN ; i ++ ) { temp -> child [ i ] = NULL ; } return temp ; } void insertRecursively ( trie * itr , string str , int i ) { if ( i < str . length ( ) ) { int index = str [ i ] - ' a ' ; if ( itr -> child [ index ] == NULL ) { itr -> child [ index ] = createNode ( ) ; } insertRecursively ( itr -> child [ index ] , str , i + 1 ) ; } else { itr -> endOfWord = true ; } } void insert ( trie * itr , string str ) { insertRecursively ( itr , str , 0 ) ; } bool isLeafNode ( trie * root ) { return root -> endOfWord != false ; } void displayContent ( trie * root , char str [ ] , int level ) { if ( isLeafNode ( root ) ) { str [ level ] = ' \0' ; cout << str << endl ; } for ( int i = CHILDREN - 1 ; i >= 0 ; i -- ) { if ( root -> child [ i ] ) { str [ level ] = i + ' a ' ; displayContent ( root -> child [ i ] , str , level + 1 ) ; } } } void display ( trie * itr ) { int level = 0 ; char str [ MAX ] ; displayContent ( itr , str , level ) ; } int main ( ) { trie * root = createNode ( ) ; insert ( root , " their " ) ; insert ( root , " there " ) ; insert ( root , " answer " ) ; insert ( root , " any " ) ; display ( root ) ; return 0 ; }