Strings from an array which are not prefix of any other string | Java implementation of the approach ; Trie node ; isEndOfWord is true if the node represents end of a word ; Returns new trie node ( initialized to NULLs ) ; Function to insert a String into trie ; While inerting a word make each isEndOfWord as false ; Check if this word is prefix of some already inserted word If it is then don 't insert this word ; If present word is not prefix of any other word then insert it ; Function to display words in Trie ; If node is leaf node , it indicates end of String , so a null character is added and String is displayed ; If NON NULL child is found add parent key to str and call the display function recursively for child node ; Driver code ; Conclass trie
import java . util . Arrays ; class GFG { static final int ALPHABET_SIZE = 26 ; static class TrieNode { TrieNode [ ] children ; boolean isEndOfWord ; TrieNode ( ) { this . children = new TrieNode [ ALPHABET_SIZE ] ; } } static TrieNode getNode ( ) { TrieNode pNode = new TrieNode ( ) ; pNode . isEndOfWord = false ; Arrays . fill ( pNode . children , null ) ; return pNode ; } static void insert ( TrieNode root , String key ) { TrieNode pCrawl = root ; for ( int i = 0 ; i < key . length ( ) ; i ++ ) { int index = key . charAt ( i ) - ' a ' ; if ( pCrawl . children [ index ] == null ) pCrawl . children [ index ] = getNode ( ) ; pCrawl . isEndOfWord = false ; pCrawl = pCrawl . children [ index ] ; } int i ; for ( i = 0 ; i < 26 ; i ++ ) { if ( pCrawl . children [ i ] != null ) { break ; } } if ( i == 26 ) { pCrawl . isEndOfWord = true ; } } static void display ( TrieNode root , char str [ ] , int level ) { if ( root . isEndOfWord ) { str [ level ] = ' \0' ; System . out . println ( str ) ; } int i ; for ( i = 0 ; i < ALPHABET_SIZE ; i ++ ) { if ( root . children [ i ] != null ) { str [ level ] = ( char ) ( i + ' a ' ) ; display ( root . children [ i ] , str , level + 1 ) ; } } } public static void main ( String [ ] args ) { String keys [ ] = { " apple " , " app " , " there " , " the " , " like " } ; int n = keys . length ; TrieNode root = getNode ( ) ; for ( int i = 0 ; i < n ; i ++ ) insert ( root , keys [ i ] ) ; char [ ] str = new char [ 100 ] ; display ( root , str , 0 ) ; } }