Sorting array of strings ( or words ) using Trie | Java 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
import java . util . * ; class GFG { static final int MAX_CHAR = 26 ; static class Trie { int index ; Trie child [ ] = new Trie [ MAX_CHAR ] ; Trie ( ) { for ( int i = 0 ; i < MAX_CHAR ; i ++ ) child [ i ] = null ; index = - 1 ; } } static void insert ( Trie root , String str , int index ) { Trie node = root ; for ( int i = 0 ; i < str . length ( ) ; i ++ ) { int ind = str . charAt ( i ) - ' a ' ; if ( node . child [ ind ] == null ) node . child [ ind ] = new Trie ( ) ; node = node . child [ ind ] ; } node . index = index ; } static boolean 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 ) { System . out . print ( arr [ node . child [ i ] . index ] + " ▁ " ) ; } preorder ( node . child [ i ] , arr ) ; } } return false ; } static 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 ) ; } public static void main ( String [ ] args ) { String arr [ ] = { " abc " , " xy " , " bcd " } ; int n = arr . length ; printSorted ( arr , n ) ; } }