Python recursion solutionGiven the same tree structure as in part I:
def traverse_recursive(node, path=list()): path.append(node.name) yield path for n in node.children: for path in traverse_recursive(n, path): yield path if path: path.pop()
The key approach is to use python
yield statement, which makes this function a generator. Here is in depth guide to generators, but in a nutshell, when python runs function which "yield"s instead of returning, two things happen:
- When function is called, then none of the function code actually executes, just a generator object is returned
- Each time generator object is iterated, function code runs until it yields - then yielded value is returned and function execution paused until the next iterator iteration
- The important thing to note is that all of the function context persists between subsequent iterations
The beauty of this technique is that traversed paths are returned to the caller as soon as they are found. Additionally, if caller wants to pause parsing of tree paths, tree traversal pauses as well. Caller can even delegate results processing to another function at some later stage by simply passing generator object over.
- Low memory footprint
- Results are available immediately
- Tree is traversed "as you(caller) go". Traversal can be paused/aborted any time.
- Recursion. On very deep trees one may have to change Python's max execution depth