Python recursion example to navigate tree data

Date: 2008-08-19 | Modified: 2009-03-25 | Tags: algorithms, python | 6 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)

6 Comments

#1 nihiliad commented on 2008-08-29:

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 2008-08-29:

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 2008-08-30:

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 2008-09-02:

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

#5 gefilte commented on 2009-06-01:

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 2009-06-01:

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


Name:	Required
Email:	Required, but not displayed
Website:	Optional
Comment:	Format using Markdown. (No HTML.) Code blocks: prefix each line by at least 4 spaces or 1 tab (and a blank line before and after) Code span: surround with backticks Blockquotes: prefix lines to be quoted with > Links: <URL> Links w/ description: [description](URL)

SaltyCrane Blog