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.

You can use this code as it is. You can add as many levels as you want. What exactly is your problem? — thefourtheye, Jan 24 '14 at 09:27
I don't know how many levels I have beforehand, so I'd like to be able to add them dynamically instead of hardcoding them — user252652, Jan 24 '14 at 09:34
this is recursion man, have you tried my answer? all you have to do is change the object type from the standard object to a dictionary — pythonian29033, Jan 24 '14 at 09:52
Could you give an example of what kind of code you'd like to write, or of some input you'd like to process into a tree? — Janne Karila, Jan 24 '14 at 11:47

thefourtheye · Accepted Answer · 2014-01-24T11:01:41.023

7

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)

edited Jan 24 '14 at 11:01

answered Jan 24 '14 at 09:52

thefourtheye

233,700
52
457
497

This helps a lot thanks. But what if I want to build the levels one by one. i.e., I don't really have all pahts beforehand. I want to build the first level, and if I have a child node of that, build another level, ...etc. – user252652 Jan 24 '14 at 10:01
He needs a recursive function man, check the tags in the question, I think he needs guidance as to how to go about building an object tree that goes N levels deep using recursion. you've got 23.4k rep, you're the expert on this – pythonian29033 Jan 24 '14 at 10:14
2

@pythonian29033 I just managed to give a basic recursive version please check :) – thefourtheye Jan 24 '14 at 11:02
@user252652 You can use either version to add the elements as and when you get data, as long as you know the `path`. – thefourtheye Jan 24 '14 at 11:02
@thefourtheye thanks, I shoulda prolly changed my answer to be that simple, but at least I got an upvote :D – pythonian29033 Jan 24 '14 at 12:46

pythonian29033 · Answer 2 · 2014-01-24T09:50:48.903

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

score 0 · Answer 3 · answered Jan 24 '14 at 09:35

0

This

root['toplevel']['secondlevel']['thirdlevel'] = 1

can also be done like this:

node = root
for key in ('toplevel', 'secondlevel'):
    node = node[key]
node['thirdlevel'] = 1

I hope that gives you an idea.

answered Jan 24 '14 at 09:35

Janne Karila

24,266
6
53
94

How do I build a tree dynamically in Python

3 Answers3

Linked