SaltyCrane Blog — Notes on JavaScript and web development

Python recursion example to navigate tree data

Date:  |  Modified:  |  Tags: algorithms, python  |  12 Comments

Here is a simple Python example using recursion to navigate a nested Python data structure. Each node in the data structure contains 0 or more children. In this simple example, I look at each node and print the "text" indented according to the nesting level within the data structure.

Update 2008-09-15: Nihiliad posted an improvement to my example in the comments. It is much simpler. I have updated my example below.

Nihiliad's (improved) method
data = {'count': 2,
        'text': '1',
        'kids': [{'count': 3,
                  'text': '1.1',
                  'kids': [{'count': 1,
                            'text': '1.1.1',
                            'kids': [{'count':0,
                                      'text': '1.1.1.1',
                                      'kids': []}]},
                           {'count': 0,
                            'text': '1.1.2',
                            'kids': []},
                           {'count': 0,
                            'text': '1.1.3',
                            'kids': []}]},
                 {'count': 0,
                  'text': '1.2',
                  'kids': []}]}

def traverse(data):
    print ' ' * traverse.level + data['text']
    for kid in data['kids']:
        traverse.level += 1
        traverse(kid)
        traverse.level -= 1

if __name__ == '__main__':
    traverse.level = 1
    traverse(data)

Results:

 1
  1.1
   1.1.1
    1.1.1.1
   1.1.2
   1.1.3
  1.2
My original (inferior) method
def outer(data):
    class Namespace: pass
    ns = Namespace()
    ns.level = 1
    
    def inner(data):
        print ' ' * ns.level + data['text']
        if data['count'] > 0:
            ns.level += 1
            for kid in data['kids']:
                inner(kid)
            ns.level -= 1

    inner(data)

if __name__ == '__main__':
    outer(data)

Comments


#1 nihiliad commented on :

You actually don't need the 'count' keys in the data dictionary, nor do you need the "if data['count'] > 0:" block. The code can be simplified even further by using a closure instead of the 'Namespace' class, eliminating the need for two ("outer" & "inner") routines:

def traverse(data):
    print ' ' * traverse.level + data['text']
    for kid in data['kids']:
        traverse.level += 1
        traverse(kid)
        traverse.level -= 1

if __name__ == '__main__':
    traverse.level = 1
    traverse(data)

I tried using your method to format the above code: http://www.saltycrane.com/blog/2008/08/django-blog-project-12-adding-pygments-syntax-highlighting/ I hope it works on comments, but the preview indicates it may not, so the indentation may be incorrect.


#2 nihiliad commented on :

As a thought, the formatting didn't work. Please visit http://nihiliad.wordpress.com/2008/08/29/simplifying-sofengs-python-recursion-example/ to see properly-indented code.


#3 Sofeng commented on :

Nihiliad, Wow, I didn't know I could create a closure in this way! Your method is definitely much simpler. I will update this post with your solution. I can also add this as a better solution to my Ex 7 at http://www.saltycrane.com/blog/2008/01/python-variable-scope-notes/ Thanks a lot.

Regarding the formatting of the comments, I am working on updating to the fresh new django comments in Django 1.0 Beta 2 and adding Markdown support. Sorry for the pain in the meantime.


#4 Eliot commented on :

nihiliad,
I updated your first comment to properly display using the newly added Markdown formatting in the comments.


#5 gefilte commented on :

Hi, I recognize this is an older post, but perhaps someone is still following it...

Would I be correct in assuming that the effect of setting an attribute value on a function would be globally scoped? In other words, this approach (Nihiliads, not the original "empty class" approach) is not thread-safe. Is that right?

Thanks, David


#6 Eliot commented on :

Hi David, sorry I don't know the answer to your question. Maybe someone else knows...


#7 saivarun commented on :

your website is very good please send me some books about python to my mail


#8 Austin G commented on :

That's great but how would you populate data with say a flat file containing 'child,parent\n' ?


#9 Brandon commented on :

A better way to handle the level variable so that the scope remains within the method:

def traverse(data, level = 1):
    print ' ' * level + data['text']
    for kid in data['kids']:
        traverse(kid, level + 1)

#10 kirankotari commented on :

Can you pls guide me from result text to json like variable data in the above example.

disqus:2486271171


#12 Govind Sharma commented on :

I want to make this type of structure using mongo and python.
Please help me out.. this is very important.

var node = {
name: 'Root',
type: 'root',
children: [{
name: 'A',
type: 'child',
children : [{
name : 'C',
type : 'child',
children : [{
name : 'E',
type : 'child'
}]
},{
name : 'D',
type : 'child'
}]
},{
name: 'B',
type: 'child'
}]
};

disqus:3612719546