Search code examples
pythontrie

Why is the root different for the same character in my trie set-up? And how can I print the trie itself?


I am setting up a trie, here is my code:

class Trie:
    def __init__(self):
        self.root = {}
        self.endSymbol = "*"

    def add(self, word):
        node = self.root
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node[self.endSymbol] = word

def multiStringSearch(smallStrings):
    trie = Trie()

    for word in smallStrings:
        trie.add(word)

    return trie

print(multiStringSearch(["abc", "mnopqr", "wyz", "no", "e", "tuuv","abb"]) 

Two questions:

  1. How can I print out the trie?
  2. For some reason, the above doesn't produce the correct trie, for example, "mnopqr" and "no" should be under the same root for the 'n', but they appear separately by the above construction.

Thanks John and Ervin for your contributions, can I just check then, which of the following would the trie set-up produce?:

enter image description here


Solution

    1. For printing out the trie:
    class Trie:
        def __init__(self):
            self.root = {}
            self.endSymbol = "*"
    
        def add(self, word):
            node = self.root
            for letter in word:
                if letter not in node:
                    node[letter] = {}
                node = node[letter]
            node[self.endSymbol] = word
    
        def __str__(self):
            return str(self.root)
    
    
    def multiStringSearch(smallStrings):
        trie = Trie()
    
        for word in smallStrings:
            trie.add(word)
    
        return trie
    
    
    if __name__ == "__main__":
        trie = multiStringSearch(["abc", "mnopqr", "wyz", "no", "e", "tuuv","abb"])
        print(trie)
    
    1. No, they should not be under the same root, because they do not share a common prefix. In your example abb and abc should be under the same root, and they are if you print out the `trie.