Search in a trie Recursively | Python3 program to traverse in bottom up manner ; Trie node ; endOfWord is true if the node represents end of a word ; Function will return the new node ( initialized to NULLs ) ; Function will insert the string in a trie recursively ; Insert a new node ; Recursive call for insertion of 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
CHILDREN = 26 NEW_LINE MAX = 100 NEW_LINE class trie : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . child = [ None for i in range ( CHILDREN ) ] NEW_LINE self . endOfWord = False NEW_LINE DEDENT DEDENT def createNode ( ) : NEW_LINE INDENT temp = trie ( ) NEW_LINE return temp NEW_LINE DEDENT def insertRecursively ( itr , str , i ) : NEW_LINE INDENT if ( i < len ( str ) ) : NEW_LINE INDENT index = ord ( str [ i ] ) - ord ( ' a ' ) NEW_LINE if ( itr . child [ index ] == None ) : NEW_LINE INDENT itr . child [ index ] = createNode ( ) ; NEW_LINE DEDENT insertRecursively ( itr . child [ index ] , str , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT itr . endOfWord = True ; NEW_LINE DEDENT DEDENT def insert ( itr , str ) : NEW_LINE INDENT insertRecursively ( itr , str , 0 ) ; NEW_LINE DEDENT def searchRecursively ( itr , str , i , len ) : NEW_LINE INDENT if ( itr == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( itr . endOfWord == True and i == len - 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT index = ord ( str [ i ] ) - ord ( ' a ' ) NEW_LINE return searchRecursively ( itr . child [ index ] , str , i + 1 , len ) NEW_LINE DEDENT def search ( root , str ) : NEW_LINE INDENT arr = [ ' ' for i in range ( len ( str ) + 1 ) ] NEW_LINE arr = str NEW_LINE if ( searchRecursively ( root , arr , 0 , len ( str ) + 1 ) ) : NEW_LINE INDENT print ( " found " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " not ▁ found " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = createNode ( ) ; NEW_LINE insert ( root , " thier " ) ; NEW_LINE insert ( root , " there " ) ; NEW_LINE insert ( root , " answer " ) ; NEW_LINE insert ( root , " any " ) ; NEW_LINE search ( root , " anywhere " ) NEW_LINE search ( root , " answer " ) NEW_LINE DEDENT