Convert tree to list of lists

[Dylan_T_Rabbit]

I have a tree structure which I need to convert to a list of lists.
The class for a node is defined as (irrelevant detail removed):

class TMoveTree:
   # The nodes of the valid moves tree
   def __init__(self, parent, data):
       self._parent = parent
       self._children = []
       self._data = data # a tuple (start, target) 

The tree represents the valid moves for a board game. The game has three dice, so the maximum depth of the tree is 4 (1 level for the root node, and 1 for each die,) and each node can have up to 15 children. After generating and pruning the tree, I have a tree like below:

ROOT
|_____ (0, 3)
         |_______ (0, 4)
         |          |_____ (0, 5)
         |          |_____ (3, 8)
         |          |_____ (4, 9)
         |
         |_______ (3, 7)
                     |_____ (0, 5)
                     |_____ (7, 12)

Each node contains a move in the form of a tuple representing the start and end board positions for a game piece  (apart from ROOT, which has (-1,-1).) I need to convert this tree into a list of lists as follows:

• Each branch should be a list of the tuples in that branch, ordered from leaf to root
  
• The lists generated from each branch are collected into a list, the order is irrelevant
  

For the tree above, this should be:

[
[(-1,-1), (0,3), (0,4), (0,5)]
[(-1,-1), (0,3), (0,4), (3,8)]
[(-1,-1), (0,3), (0,4), (4,9)]
[(-1,-1), (0,3), (3,7), (0,5)]
[(-1,-1), (0,3), (3,7), (7,12)]
]

I have the following function so far:

def tree2list(self):
       if len(self._children) == 0:
           return [self._data]
       else:
           node_list = [[self._data] + child.tree2list() for child in self._children]
           return node_list

Which outputs:

Output:
[[(-1, -1), [(0, 3), [(0, 4), (0, 5)], [(0, 4), (3, 8)], [(0, 4), (4, 9)]], [(0, 3), [(3, 7), (0, 5)], [(3, 7), (7, 12)]]]]

Reformatted for clarity:

[inline][
[(-1, -1), [(0, 3), [(0, 4), (0, 5)],
                    [(0, 4), (3, 8)],
                    [(0, 4), (4, 9)]
           ],
           [(0, 3), [(3, 7), (0, 5)],
                    [(3, 7), (7, 12)]
           ]
]
][/inline]

How can I get my 'tree2list' function to output the desired list of lists?

Thanks for any help

Dylan

[ichabod801]

You need to pass the data down the recursion and use it at the end. Something like this:

def tree2list(self, prev_data = []):
    if self._children:
        child_data = []
        for child in self.children:
            child_data.extend(child.tree2list(prev_data + self._data))
        return child_data
    else:
        return [prev_data + self._data]

Untested code. Use at your own risk.

[Dylan_T_Rabbit]

Thank you!
I'll put that to the test and update the post with results.