14.7.2. Demo: Navigating Trees (recursion)

Structure of Comments & Replies

Let’s look at our example from before of comments and replies:

When we want to represent Trees (like comments and replies) in code, one way of doing so is by using dictionaries.

Our initial comment will be a dictionary with text (the comment text), and replies (a list of dictionaries).

Each of those replies will in turn be a dictioary with text (the reply text), and replies to that reply (a list of dictionaries).

And so on.

Below is code to store that in a variable (though it looks kind of messy):

comment_about_exam = {
    'text': 'That last exam sure was hard!',
    'replies':[{
        'text': 'It sure was hard, what score did you get? ',
        'replies': [{
            'text': 'I got a 67% :(',
            'replies': []
        },{
            'text': 'I got a 73%',
            'replies': []
        }]
    }, {
        'text': 'I didn\'t think it was that bad',
        'replies': [{
            'text': 'how was that not a super hard exam?',
            'replies': []
        }, {
            'text': 'of course you didn\'t',
            'replies': [{
                'text': 'what\'s that supposed to mean?',
                'replies': [{
                    'text': 'you\'re an overacheiver',
                    'replies': [{
                        'text': 'and that\'s bad how?',
                        'replies': []
                    }]
                }]
            }]
        }]
    }]
}

We’ll also make a function that will help us display a message in a box that is indented over. Don’t worry about the details, but this uses HTML display styling, which is how websites do styling.

from IPython.display import HTML, Image, display
import html
def display_indented(text, left_margin=0):
    display(
        HTML(
            "<pre style='border:solid 1px;padding:3px;margin-left:"+ str(left_margin) + "px'>" + 
            html.escape(text) + 
            "</pre>"
        )
    )

The function above takes the text to be displayed, and optionally the left_margin for how much to indent the text box.

Below are some examples of how it works:

display_indented("Here is an example")

Here is an example

display_indented("Here is an example with an left_margin of 20", left_margin=20)

Here is an example with an left_margin of 20

Navigating tree

Now let’s consider how we can navigate this tree of comments and replies.

First, we can just print out the initial comment (the root):

display_indented(comment_about_exam['text'])

That last exam sure was hard!

Navigate with for loops

If we want to print the initial comment, and just the replies to that comment, we can use a for loop, like this:

display_indented(comment_about_exam['text'])

for reply in comment_about_exam['replies']:
    display_indented(reply['text'], left_margin=20)

That last exam sure was hard!

It sure was hard, what score did you get? 

I didn't think it was that bad

If we also want to include the replies to those initial replies, we can put another for loop inside of there:

display_indented(comment_about_exam['text'])

for reply in comment_about_exam['replies']:
    display_indented(reply['text'], left_margin=20)
    
    for reply_reply in reply['replies']:
        display_indented(reply_reply['text'], left_margin=40)

That last exam sure was hard!

It sure was hard, what score did you get? 

I got a 67% :(

I got a 73%

I didn't think it was that bad

how was that not a super hard exam?

of course you didn't

If we want to get all of the replies in our example though, we’ll need to have a for loop for each level, but the code is going to be getting messy:

display_indented(comment_about_exam['text'])

for reply in comment_about_exam['replies']:
    display_indented(reply['text'], left_margin=20)
    
    for reply_reply in reply['replies']:
        display_indented(reply_reply['text'], left_margin=40)
        
        for reply_reply_reply in reply_reply['replies']:
            display_indented(reply_reply_reply['text'], left_margin=60)
            
            for reply_reply_reply_reply in reply_reply_reply['replies']:
                display_indented(reply_reply_reply_reply['text'], left_margin=80)
                
                for reply_reply_reply_reply_reply in reply_reply_reply_reply['replies']:
                    display_indented(reply_reply_reply_reply_reply['text'], left_margin=100)

That last exam sure was hard!

It sure was hard, what score did you get? 

I got a 67% :(

I got a 73%

I didn't think it was that bad

how was that not a super hard exam?

of course you didn't

what's that supposed to mean?

you're an overacheiver

and that's bad how?

for loops didn’t work great

Our code was messy, and if there were even more levels, we’d need even more for loops. This could go on endlessly.

Navigate with recursion: a function that calls itself

We can use a clever programming trick that will work better.

We make a function that prints a comment and all the replies (print_comment_and_replies). So our function will first print the text of the comment, and then it will go through each reply, but instead of printing the reply directly, there is a function that will print that comment and all replies to it: print_comment_and_replies (which is the function we are writing).

This trick can be confusing to understand (and it’s ok if you don’t), but let’s look at it again in psuedocode:

The function print_comment_and_replies does the following

1. Print the text of the comment

2. For each of the replies to that comment, use the print_comment_and_replies function to print it out

So, we will call print_comment_and_replies with our initial comment, and that function will then call print_comment_and_replies for each of the replys to that comment, and then those new calls to print_comment_and_replies will call print_comment_and_replies for all the replies to those comments, and so on, until all the comments are printed out.

Note: In computer science terms, this is called a “depth-first search” algorithm

The actual code for print_comment_and_replies is here:

def print_comment_and_replies(comment):
    # print comment
    display_indented(comment['text'])
    
    #print replies (and the replies of those, etc.)
    for reply in comment['replies']:
        print_comment_and_replies(reply)

And we can test it out on our comment and see it work

print_comment_and_replies(comment_about_exam)

That last exam sure was hard!

It sure was hard, what score did you get? 

I got a 67% :(

I got a 73%

I didn't think it was that bad

how was that not a super hard exam?

of course you didn't

what's that supposed to mean?

you're an overacheiver

and that's bad how?

In the above result, there were no indents, but we can use another trick (getting more confusing) where we track how many indents to make when the function is called (by default, it starts at 0). When the function calls itself to print the replies, we adde:

def print_comment_and_replies(comment, num_indents=0):
    # print indented comment
    display_indented(comment['text'], left_margin=num_indents*20)
    
    #print replies (and the replies of those, etc.)
    for reply in comment['replies']:
        print_comment_and_replies(reply, num_indents = num_indents + 1)

And when we test this out, we can see the result

print_comment_and_replies(comment_about_exam)

That last exam sure was hard!

It sure was hard, what score did you get? 

I got a 67% :(

I got a 73%

I didn't think it was that bad

how was that not a super hard exam?

of course you didn't

what's that supposed to mean?

you're an overacheiver

and that's bad how?