List of branches of a Python tree

Question

I have a tree of Python objects. The tree is defined intrinsically: each object has a list (potentially empty) of children. I would like to be able to print a list of all paths from the root to each leaf.

In the case of the tree above, this would mean:

result = [
          [Node_0001,Node_0002,Node_0004],
          [Node_0001,Node_0002,Node_0005,Node_0007],
          [Node_0001,Node_0003,Node_0006],
         ]

The nodes must be treated as objects and not as integers (only their integer ID is displayed). I don't care about the order of branches in the result. Each node has an arbitrary number of children, and the level of recursion is not fixed either.

I am trying a recursive approach:

def get_all_paths(node):
    if len(node.children)==0:
        return [[node]]
    else:
        return [[node] + get_all_paths(child) for child in node.children]

but I end-up with nested lists, which is not what I want:

[[Node_0001,
  [Node_0002, [Node_0004]],
  [Node_0002, [Node_0005, [Node_0007]]]],
 [Node_0001, [Node_0003, [Node_0006]]]]

Any help would be gladly welcomed, this problem is driving me crazy :p

Thanks

Consider using inorder traversal. Left-Root-Right – Krishnachandra Sharma Dec 19 '17 at 07:36 — Krishnachandra Sharma, Dec 19 '17 at 07:36

user2390182 · Accepted Answer · 2017-12-19T07:42:57.813

4

I think this is what you are trying:

def get_all_paths(node):
    if len(node.children) == 0:
        return [[node]]
    return [
        [node] + path for child in node.children for path in get_all_paths(child)
    ]

For each child of a node, you should take all paths of the child and prepend the node itself to each path. You prepended the node to the list of paths, not every path individually.

edited Dec 19 '17 at 07:42

answered Dec 19 '17 at 07:36

user2390182

72,016
6
67
89

Works like a charm, thanks :D I get: `[[Node_0001, Node_0002, Node_0004], [Node_0001, Node_0002, Node_0005, Node_0007], [Node_0001, Node_0003, Node_0006]]` – Alex Dec 19 '17 at 07:55
I like this approach of first finding all the branch combinations, then doing operations on those branches (e.g. find the total length of the branch). Most other solutions I see for tree walking seem to perform operations during the tree walking and the code becomes pretty messy. – KCharlie Jun 22 '22 at 18:32

List of branches of a Python tree

1 Answers1

Linked