Homework answers / question archive / class Trie: class TrieNode: def __init__(self): self

class Trie: class TrieNode: def __init__(self): self

Computer Science

Share With

class Trie:
    class TrieNode:
        def __init__(self):
            self.children = {}
            self.endOfString = False

    def __init__(self):
        self.root = self.TrieNode()

    def insert(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = self.TrieNode()
            cur = cur.children[c]
        cur.endOfString = True

    def search(self, word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.endOfString


    # function returns the list of all words in the Trie in alphabetical order
    def recursive_get_all(self, current, str):
        reslut_list = []
        if current.endOfString == True: 
            reslut_list.append(str)  
            
        for i in current.children:
            list = self.recursive_get_all( current.children[i] , str+i )
            if len(list) > 0:
                reslut_list += list
        return reslut_list
    def get_all(self):
        return sorted( self.recursive_get_all(self.root, "") )

    # function returns the list of all words that begin with prefix 
    # in the Trie in alphabetical order
    def recursive_begins_with(self, trie, pre, str, p):
        reslut_list = []
        if trie.endOfString and p >= len(pre):
            reslut_list.append(str)
        
        for i in trie.children:
            if p >= len(pre) or i == pre[p]:
                list = self.recursive_begins_with( trie.children[i] , pre , str+i , p+1 )
                if len(list) != 0:
                    reslut_list += list
        return reslut_list
    def begins_with(self, prefix):
        return sorted(self.recursive_begins_with(self.root, prefix, "", 0))

This is the code that implements the Trie algorithm. How to implement def get_all(self) and def begin_with(self, prefix) using a for loop without using a recursive method?

How can I implement the two functions mentioned using iterative method?