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
– thefourtheye, Commented Jan 24, 2014 at 9: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
– user252652, Commented Jan 24, 2014 at 9: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
– pythonian29033, Commented Jan 24, 2014 at 9: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
– Janne Karila, Commented Jan 24, 2014 at 11:47

thefourtheye · Accepted Answer · 2014-01-24 11:01:41Z

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, 2014 at 11:01

answered Jan 24, 2014 at 9:52

thefourtheye

241k53 gold badges466 silver badges505 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user252652 Over a year ago

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.

pythonian29033 Over a year ago

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

thefourtheye Over a year ago

@pythonian29033 I just managed to give a basic recursive version please check :)

thefourtheye Over a year ago

@user252652 You can use either version to add the elements as and when you get data, as long as you know the path.

pythonian29033 Over a year ago

@thefourtheye thanks, I shoulda prolly changed my answer to be that simple, but at least I got an upvote :D

pythonian29033 · Accepted Answer · 2014-01-24 09:50:48Z

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

Janne Karila · Accepted Answer · 2014-01-24 09:35:39Z

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, 2014 at 9:35

Janne Karila

25.3k6 gold badges59 silver badges97 bronze badges

Collectives™ on Stack Overflow

How do I build a tree dynamically in Python

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related