Sorting array of strings ( or words ) using Trie | C ++ program to sort an array of strings using Trie ; index is set when node is a leaf node , otherwise - 1 ; ; to make new trie ; function to insert in trie ; taking ascii value to find index of child node ; making new path if not already ; go to next node ; Mark leaf ( end of word ) and store index of word in arr [ ] ; function for preorder traversal ; if leaf node then print key ; insert all keys of dictionary into trie ; print keys in lexicographic order ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX_CHAR = 26 ; struct Trie { int index ; Trie * child [ MAX_CHAR ] ; Trie ( ) { for ( int i = 0 ; i < MAX_CHAR ; i ++ ) child [ i ] = NULL ; index = -1 ; } } ; void insert ( Trie * root , string str , int index ) { Trie * node = root ; for ( int i = 0 ; i < str . size ( ) ; i ++ ) { char ind = str [ i ] - ' a ' ; if ( ! node -> child [ ind ] ) node -> child [ ind ] = new Trie ( ) ; node = node -> child [ ind ] ; } node -> index = index ; } bool preorder ( Trie * node , string arr [ ] ) { if ( node == NULL ) return false ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( node -> child [ i ] != NULL ) { if ( node -> child [ i ] -> index != -1 ) cout << arr [ node -> child [ i ] -> index ] << endl ; preorder ( node -> child [ i ] , arr ) ; } } } void printSorted ( string arr [ ] , int n ) { Trie * root = new Trie ( ) ; for ( int i = 0 ; i < n ; i ++ ) insert ( root , arr [ i ] , i ) ; preorder ( root , arr ) ; } int main ( ) { string arr [ ] = { " abc " , " xy " , " bcd " } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printSorted ( arr , n ) ; return 0 ; }