Print Strings In Reverse Dictionary Order Using Trie | Python3 program to print array of string in reverse dictionary order using trie ; Trie node ; endOfWord is true if the node represents end of a word ; Function will return the new node initialized NONE ; Initialize null to the all child ; Function will insert the string in a trie recursively ; Create 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 check whether the node is leaf or not ; Function to display the content of trie ; If node is leaf node , it indicates end of string , so a null character is added and string is displayed ; Assign a null character in temporary string ; check if NON NONE child is found add parent key to str and call the display function recursively for child node ; Function call for displaying content ; Driver code ; After inserting strings , trie will look like root / \ a t | | n h | \ | s y e | | \ w i r | | | e r e | r
CHILDREN = 26 NEW_LINE MAX = 100 NEW_LINE class trie : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . child = [ 0 for i in range ( CHILDREN ) ] NEW_LINE self . endOfWord = False ; NEW_LINE DEDENT DEDENT def createNode ( ) : NEW_LINE INDENT temp = trie ( ) ; NEW_LINE temp . endOfWord = False ; NEW_LINE for i in range ( CHILDREN ) : NEW_LINE INDENT temp . child [ i ] = None ; NEW_LINE DEDENT 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 isLeafNode ( root ) : NEW_LINE INDENT return root . endOfWord != False ; NEW_LINE DEDENT def displayContent ( root , str , level ) : NEW_LINE INDENT if ( isLeafNode ( root ) ) : NEW_LINE INDENT print ( " " . join ( str [ : level ] ) ) NEW_LINE DEDENT for i in range ( CHILDREN - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( root . child [ i ] ) : NEW_LINE INDENT str [ level ] = chr ( i + ord ( ' a ' ) ) ; NEW_LINE displayContent ( root . child [ i ] , str , level + 1 ) ; NEW_LINE DEDENT DEDENT DEDENT def display ( itr ) : NEW_LINE INDENT level = 0 ; NEW_LINE str = [ ' ' for i in range ( MAX ) ] ; NEW_LINE displayContent ( itr , str , level ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = createNode ( ) ; NEW_LINE insert ( root , " their " ) ; NEW_LINE insert ( root , " there " ) ; NEW_LINE insert ( root , " answer " ) ; NEW_LINE insert ( root , " any " ) ; NEW_LINE display ( root ) ; NEW_LINE DEDENT