Construct A Tree From A List With Levels

I have some data(Python list of dicts) which looks like: [ {'value': 'A', 'level': 0}, {'value': 'B', 'level': 1}, {'value': 'C', 'level': 2}, {'value': 'D', 'level

Solution 1:

The code should be simple. Your scheme implies there is an order to the children, so I will use a list.

In [8]: classNode:
   ...:     def__init__(self, val=None):
   ...:         self.value = val
   ...:         self.children = []
   ...:     def__repr__(self):
   ...:         return"<Node {}>".format(self.value)
   ...:

The algorithm is also simple. Start at the root. Iterate over the data. While you are less than "level" nodes deep, continue moving down the children going to the last child appended attempting to go down the last node in children. If attempting to index into the last child fails, then we know we are where we have to be (assuming the input is well behaved!) and we append a new node with the value "value". If you don't fail and make it to "level", append a new node with the value "value". Return to the root and repeat while you are not done iterating over the data.

In [9]: root = Node()

In [10]: for record in data:
    ...:     last = root
    ...:     for _ in range(record['level']):
    ...:         last = last.children[-1]
    ...:     last.children.append(Node(record['value']))
    ...:

Now, to check out our tree:

In[12]: root.childrenOut[12]: [<Node A>, <Node G>]In[13]: root.children[0].childrenOut[13]: [<Node B>, <Node D>]In[14]: root.children[0].children[1].childrenOut[14]: [<Node E>, <Node F>]In[15]: root.children[1].childrenOut[15]: [<Node H>]In[16]: root.children[1].children[0].childrenOut[16]: []

Using your handy print_tree function:

In [24]: def print_tree(root, depth=0):
    ...:     for child in root.children:
    ...:         print('  ' * depth + '%r' % child)
    ...:         print_tree(child, depth + 1)
    ...:

In [25]: print_tree(root)
<NodeA><NodeB><NodeC><NodeD><NodeE><NodeF><NodeG><NodeH>