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': {'_':

Solution 1:

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']

Solution 2:

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.

defbuild_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

classnode:
    def__init__(self, val):
        self.val = val
        self.children = []