N-Ary Tree Traversal That Includes Paths to Internal Nodes

Question

The accepted answer in the following post provides all root-to-leaf paths in an n-ary tree: print all the path of n-ary tree python. How could you modify the code in the above answer (also included below) to also include paths from root to internal nodes? For example, in the tree provided in the post, the complete list would be:

[10, 2] #path from root to internal node
[10, 4] #path from root to internal node
[10, 2, 15] #path from root to leaf
[10, 2, 20] #...
[10, 2, 25]
[10, 2, 30]
[10, 4, 45]
[10, 4, 50]
[10, 4, 55]
[10, 4, 60]

How could you modify this program to complete this task?

def traverse(node, path = []):
    path.append(node.data)
    if len(node.child) == 0:
        print(path)
        path.pop()
    else:
        for child in node.child:
            traverse(child, path)
        path.pop()

Move the`print` up above the `if` statement (and de-indent it). — Tom Karzes, Dec 31 '19 at 15:57
Thanks! That worked perfectly. Not sure how I didn't catch that. — Luke Poeppel, Dec 31 '19 at 15:59
Also, there is no need for the code to replicate the `path.pop()` call. It would be better to move it below the `if-else` and only have a single copy of it. (Functionally equivalent.) — Tom Karzes, Dec 31 '19 at 15:59

ggorlen · Accepted Answer · 2020-01-24T18:31:32.877

This is a pretty simple modification; keep the DFS but print at every node instead of only the leaves. For each recursive call frame, push the root node, yield the path, recurse on every child and then pop the root once all children have been visited.

traverse is a poor function name because it doesn't describe what kind of traversal is being done.

def all_tree_paths(node, path=[]):
    path.append(node)
    yield path[:]

    for child in node.child:
        yield from all_tree_paths(child, path)

    path.pop()

if __name__ == "__main__":
    from collections import namedtuple

    Node = namedtuple("Node", "data child")
    """  a
       / | \
      b  c  d
     /     / \
    e     f   g
    """
    tree = Node(
        "a",
        [
            Node(
                "b", 
                [
                    Node("e", [])
                ]
            ),
            Node("c", []),
            Node(
                "d", 
                [
                    Node("f", []),
                    Node("g", [])
                ]
            ) 
        ]
    )
    print([[x.data for x in path] for path in all_tree_paths(tree)])

Output:

['a']
['a', 'b']
['a', 'b', 'e']
['a', 'c']
['a', 'd']
['a', 'd', 'f']
['a', 'd', 'g']

With this in mind, I think the original is clearer as:

def all_root_to_leaf_paths(node, path=[]):
    path.append(node)

    if not node.child:
        yield path[:]

    for child in node.child:
        yield from traverse(child, path)

    path.pop()

if len(node.child) == 0: should be if node.child; the else is superfluous; path.pop() only needs to be called at the end of the function instead of once in each branch; and prefer returning a generator to producing a side effect like printing, which cripples reusability.

N-Ary Tree Traversal That Includes Paths to Internal Nodes

1 Answers1