CODEWITHSUNDEEP
pythonalgorithmpython-3.xtraversaltrie
Brett
Brett

Reputation: 386

Python Trie: how to traverse it to build list of all words?

I have created a trie tree as im learning python, here is the trie output

{'a': {'b': {'c': {'_': '_'}}}, 'b': {'a': {'x': {'_': '_'}, 'r': {'_': '_', 'z': {'_': '_'}}, 'z': {'_': '_'}}}, 'h': {'e': {'l': {'l': {'o': {'_': '_'}}}}}}

I am unable to list all the words back out of the trie, I'm obviously not understanding something simple, below is my code to create the trie and add to the trie as well as check if words are present in the trie. The method list is my poor attempt to list words, Its only getting the first letter of each word at the moment. Any advice would be super. 

# Make My trie
def make_trie(*args):
    """
    Make a trie by given words.
    """
    trie = {}
    for word in args:
        if type(word) != str:
            raise TypeError("Trie only works on str!")
        temp_trie = trie
        for letter in word:
            temp_trie = temp_trie.setdefault(letter, {})
        temp_trie = temp_trie.setdefault('_', '_')
    return trie


# Is a word in the trie
def in_trie(trie, word):
    """
    Detect if word in trie.
    :param word:
    :param trie:
    """
    if type(word) != str:
        raise TypeError("Trie only works on str!")
    temp_trie = trie
    for letter in word:
        if letter not in temp_trie:
            return False
        temp_trie = temp_trie[letter]
    return True


# add to the trie
def add(trie, *args):
    for word in args:
        if type(word) != str:
            raise TypeError("Trie only works on str!")
        temp_trie = trie
        for letter in word:
            temp_trie = temp_trie.setdefault(letter, {})
        temp_trie = temp_trie.setdefault('_', '_')
    return trie


# My Attempt to list out words
def list(obj, text, words):
   str = ""
   temp_trie = obj
   for index, word in enumerate(temp_trie):
       print(temp_trie[word])



if __name__ == '__main__':
    trie = make_trie('hello', 'abc', 'baz', 'bar', 'barz')
    # print(trie)
    # get_file()
    words = []
    # list(trie, "", words)
    print(in_trie(trie, 'bar'))
    print(in_trie(trie, 'bab'))
    print(in_trie(trie, 'zzz'))
    add(trie, "bax")
    print(in_trie(trie, 'bax'))
    print(in_trie(trie, 'baz'))
    print(trie)
    list(trie, "", 'hello')

The expected output i would like is a list of words present in the trie like so

content = ['hello', 'abc', 'baz', 'bar', 'barz']

Upvotes: 3

Views: 8332

Answers (2)

Nic Scozzaro
Nic Scozzaro

Reputation: 7353

In case this is useful to someone, here's a python implementation for generating all strings in a trie if you have a class-based trie.

def build_all(root):
    l = []
    if root:
        if root.children: 
            for node in root.children: 
                for s in build_all(node):
                    l.append(str(node.val) + s)
        else: 
            l.append('')
    return l

class node:
    def __init__(self, val):
        self.val = val
        self.children = []

Upvotes: 2

Francesco
Francesco

Reputation: 4250

You should write a recursive function that searches the tree

def list_words(trie):
    my_list = []
    for k,v in trie.items():
        if k != '_':
            for el in list_words(v):                
                my_list.append(k+el)
        else:
            my_list.append('')
    return my_list

example output

>>> trie = {'a': {'b': {'c': {'_': '_'}}}, 'b': {'a': {'x': {'_': '_'}, 'r': {'_': '_', 'z': {'_': '_'}}, 'z': {'_': '_'}}}, 'h': {'e': {'l': {'l': {'o': {'_': '_'}}}}}}
>>> print(list_words(trie))
['abc', 'hello', 'bax', 'barz', 'bar', 'baz']

Upvotes: 13

Related Questions