How do I build a tree dynamically in Python

Question

A beginner Python/programming question... I'd like to build a tree structure in Python, preferably based on dictionaries. I found code that does this neatly:

Tree = lambda: collections.defaultdict(Tree)
root = Tree()

This can easily be populated like:

 root['toplevel']['secondlevel']['thirdlevel'] = 1
 root['toplevel']['anotherLevel'] = 2
 ...etc.

I'd like to populate the levels/leaves dynamically so that I can add as many levels as needed, and where the leaves can be at any level. How do I do that?

Any help is greatly appreciated.

Answer 1

You can simply do it with a utility function, like this

def add_element(root, path, data):
    reduce(lambda x, y: x[y], path[:-1], root)[path[-1]] = data

You can use it, like this

import collections
tree = lambda: collections.defaultdict(tree)
root = tree()
add_element(root, ['toplevel', 'secondlevel', 'thirdlevel'], 1)
add_element(root, ['toplevel', 'anotherlevel'], 2)
print root

Output

defaultdict(<function <lambda> at 0x7f1145eac7d0>,
    {'toplevel': defaultdict(<function <lambda> at 0x7f1145eac7d0>,
       {'secondlevel': defaultdict(<function <lambda> at 0x7f1145eac7d0>,
            {'thirdlevel': 1}),
        'anotherlevel': 2
       })
    })

If you want to implement this in recursive manner, you can take the first element and get the child object from current root and strip the first element from the path, for the next iteration.

def add_element(root, path, data):
    if len(path) == 1:
        root[path[0]] = data
    else:
        add_element(root[path[0]], path[1:], data)

Answer 2

aah! this was a problem for me when I started coding as well, but the best of us come across this early.

Note; this is for when your tree is going N levels deep. where N is between 0 and infinite, ie; you don't know how deep it can go; it may only have a first level, or it may go up to a 20th level

your problem is a general programming problem; reading in a tree that could be any number of levels deep and the solution to that is; Recursion.

whenever reading in a tree structure, you have to;

1 - build up an object 2 - check whether the object has children 2a - if the object has children, do steps 1 and 2 for each child.

here's a code template in python for doing this;

def buildTree(treeObject):
   currObject = Hierarchy()
   currObject.name = treeObject.getName()
   currObject.age = treeObject.getAge()
   #as well as any other calculations and values you have to set for that object

   for child in treeObject.children:
      currChild = buildTree(child)
      currObject.addChild(currChild)
   #end loop

   return currObject