Search in a trie Recursively | CPP program to search in a trie ; Trie node ; endOfWord is true if the node represents end of a word ; Function will return the new node ( initialized to NULLs ) ; initially assign null to the all child ; function will insert the string in a trie recursively ; Insert a new node ; Recursive call for insertion of a string ; Make the endOfWord true which represents the end of string ; Function call to insert a string ; Function call with necessary arguments ; Function to search the string in a trie recursively ; When a string or any character of a string is not found ; Condition of finding string successfully ; Return true when endOfWord of last node containes true ; Recursive call and return value of function call stack ; Function call to search the string ; If string found ; Driver code ; Function call to insert the string ; Function call to search the string
#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 searchRecursively ( trie * itr , char str [ ] , int i , int len ) { if ( itr == NULL ) return false ; if ( itr -> endOfWord == true && i == len - 1 ) { return true ; } int index = str [ i ] - ' a ' ; return searchRecursively ( itr -> child [ index ] , str , i + 1 , len ) ; } void search ( trie * root , string str ) { char arr [ str . length ( ) + 1 ] ; strcpy ( arr , str . c_str ( ) ) ; if ( searchRecursively ( root , arr , 0 , str . length ( ) + 1 ) ) cout << " found " << endl ; else { cout << " not ▁ found " << endl ; } } int main ( ) { trie * root = createNode ( ) ; insert ( root , " thier " ) ; insert ( root , " there " ) ; insert ( root , " answer " ) ; insert ( root , " any " ) ; search ( root , " anywhere " ) ; search ( root , " answer " ) ; return 0 ; }