Strings from an array which are not prefix of any other string | C ++ 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 ; Construct trie
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int ALPHABET_SIZE = 26 ; struct TrieNode { struct TrieNode * children [ ALPHABET_SIZE ] ; bool isEndOfWord ; } ; struct TrieNode * getNode ( void ) { struct TrieNode * pNode = new TrieNode ; pNode -> isEndOfWord = false ; for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) pNode -> children [ i ] = NULL ; return pNode ; } void insert ( struct TrieNode * root , string key ) { struct TrieNode * pCrawl = root ; for ( int i = 0 ; i < key . length ( ) ; i ++ ) { int index = key [ i ] - ' a ' ; if ( ! pCrawl -> children [ index ] ) pCrawl -> children [ index ] = getNode ( ) ; pCrawl -> isEndOfWord = false ; pCrawl = pCrawl -> children [ index ] ; } int i ; for ( i = 0 ; i < 26 ; i ++ ) { if ( pCrawl -> children [ i ] ) { break ; } } if ( i == 26 ) { pCrawl -> isEndOfWord = true ; } } void display ( struct TrieNode * root , char str [ ] , int level ) { if ( root -> isEndOfWord ) { str [ level ] = ' \0' ; cout << str << endl ; } int i ; for ( i = 0 ; i < ALPHABET_SIZE ; i ++ ) { if ( root -> children [ i ] ) { str [ level ] = i + ' a ' ; display ( root -> children [ i ] , str , level + 1 ) ; } } } int main ( ) { string keys [ ] = { " apple " , " app " , " there " , " the " , " like " } ; int n = sizeof ( keys ) / sizeof ( string ) ; struct TrieNode * root = getNode ( ) ; for ( int i = 0 ; i < n ; i ++ ) insert ( root , keys [ i ] ) ; char str [ 100 ] ; display ( root , str , 0 ) ; return 0 ; }