Lets recall our data structure first:
class TreeNode(object): def __init__(self, name): self.children = list() self.name = name root = TreeNode("Root") root.children.extend( (TreeNode("Fruits"), TreeNode("Berries")) ) root.children.children.extend( (TreeNode("Apple"), TreeNode("Peach")) ) root.children.children.extend( (TreeNode("Cherry"), TreeNode("Mullberry")) )The task: Find all paths of the tree from root to leafs.
The looping solution
def traverse(node): to_crawl = deque() lastlevel = curlevel = 0 to_crawl.append((curlevel, node)) breadcrumb = list() while to_crawl: curlevel, curnode = to_crawl.popleft() while lastlevel and lastlevel >= curlevel: breadcrumb.pop() lastlevel -= 1 breadcrumb.append(curnode.name) yield breadcrumb to_crawl.extendleft([ (curlevel+1, c) for c in curnode.children ]) lastlevel = curlevelThe idea is to use excellent deque data structure, which can be thought of a list that can be efficiently appended/popped from both left and right.
Again, lets use it:
for breadcrumb in traverse(root): print breadcrumbWhich will print:
['Root'] ['Root', 'Berries'] ['Root', 'Berries', 'Mullberry'] ['Root', 'Berries', 'Cherry'] ['Root', 'Fruits'] ['Root', 'Fruits', 'Peach'] ['Root', 'Fruits', 'Apple']Cautious reader will note that the tree is indeed traversed but in the reversed order. The reason is when one extends the deque from left, and consequently pops out items out (from left again) it creates LIFO order, effectively reversing the children processing order. The fix would be to originally insert the children to deque in the reverse order. So instead of:
to_crawl.extendleft([ (curlevel+1, c) for c in curnode.children ])we can manually insert children in the reversed order like this:
to_crawl.extendleft([ (curlevel+1, curnode.children[i]) for i in xrange(len(curnode.children)-1, -1, -1) ])
path buffer. About
Same as with python recursion solution, but even better - no recursion here.
The only disadvantage I can spot is the fact that we hold references to the children of the nodes we crawl. On extremely shallow and wide trees this can raise the memory footprint almost to