Retrieving branches from a nested dictionary

Question

I have a python nested dictionary (basically a trie structure) with sentences as branches - each node is a word. Something like this:

What is the most efficient way to retrieve all branches from root to the tips (sentences)? That is, I want to have all the possible sentences (I have a dog, I have a shotgun, I don't like Elvis). Branch (sentence) length in not a fixed value.

Answer 1

You should do a depth first search and recursively yield the tokens of the sentence. For example, using a generator:

def yield_sentences(node):
    if node.is_leaf():
        yield node.word
    else:
        for child in node.children:
            for sentence in yield_sentences(child):
                yield '{} {}'.format(node.word, sentence)

Usage:

>>> class Node(object):
...     def __init__(self, word, *children):
...             self.word = word
...             self.children = children
...     def is_leaf(self):
...             return not self.children
... 
>>> tree = Node('I', Node('have', Node('a', Node('dog'), Node('shotgun'))), Node("don't", Node('like', Node('Elvis'))))
>>> #tree is now your example tree
>>> list(yield_sentences(tree))
['I have a dog', 'I have a shotgun', "I don't like Elvis"]