Recursively DFS print a nested list

Question

I am trying to use Python to print the nested lists in such a way that we can have multiple copies of them.

My question is: How to properly print this recursively in DFS with x[0] as the parent, and x[1:] as the children?

For example, I have this input

['1', ['2', ['3', ['4', ['5', ['6', ['7']], ['8', ['9']]]]]]]

And it can be expanded to visualize in this structure:

I am trying to have both printed recursively and expected to have a result that looks like this, with the entire path printed out.

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 9

But actually end up getting this

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
5 -> 8 -> 9

Here is my code snippet

def __print(chains: List):
    """
    Assuming the input list where index 0 is the source, and index 1 is its
    children paths.
    """

    if (len(chains) == 0):
        return
    elif (len(chains) == 1):
        # reaching the end
        print("{0}".format(chains[0]))
        return
    else:
        # everything after index 0 is considered children
        children = chains[1:]

        # has children
        for child in children:
            print("{0} -> ".format(chains[0]), end='')
            __print(child)

user_6243352 · Answer

Your approach looks theoretically awesome, because you don't need to keep additional state. But there's a problem with not keeping state. Let's say you're at a parent node. There's no way to know how many times you should print this node's value, because you'd have to traverse way down into the tree to figure out how many leaf nodes it's ultimately the root of. The lack of newlines complicates things further.

So I don't see an obvious way around passing the path so far into the child calls. When you hit a terminal node, simply print the path that brought you here. Otherwise, push the current node onto the path and pass it into the recursive calls, then pop it after all children have been explored.

I don't like print in a function. That prohibits the caller from doing anything useful with the result. Better to return a generator and let the caller do what they want with it.

As an optimization, you can use one list throughout, only copying when it's time to yield a path.

def find_paths(chains, path=None):
    if path is None:
        path = []

    if not chains:
        return

    path.append(chains[0])

    if len(chains) == 1:
        yield tuple(path)
    else:
        for child in chains[1:]:
            yield from find_paths(child, path)

    path.pop()


if __name__ == "__main__":
    tree = ["1", ["2", ["3", ["4", ["5", ["6", ["7"]], ["8", ["9"]]]]]]]

    for path in find_paths(tree):
        print(" -> ".join(path))

The additional space cost here is O(tree depth).

Another thing: mixed-type data structures are hard to work with. This structure would be easier to deal with in the following typical tree format that uses a dictionary to separate node payload from children:

{
    "value": "1",
    "children": [
        {
            "value": "2",
            "children": [...],
        },
    ],
}

This makes it simple to get at the children; no need to slice, which is a waste of time and space, or have to do type()/isinstance() calls to figure out what's what (in your case, the first element is a string and the rest are lists, avoiding type-checking, but it's getting close to nasty territory...).

Recursively DFS print a nested list

1 Answers