SaltyCrane Blog — Notes on JavaScript and web development

Python recursion example to navigate tree data

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': '',
                                      '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.level -= 1

if __name__ == '__main__':
    traverse.level = 1


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']:
            ns.level -= 1


if __name__ == '__main__':


#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.level -= 1

if __name__ == '__main__':
    traverse.level = 1

I tried using your method to format the above code: 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 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 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 :

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.


#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'