Demo: Navigating Trees (recursion)
Contents
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 tweet 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 in 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 tweet (the root):
display_indented(comment_about_exam['text'])
That last exam in sure was hard!
Navigate with for loops#
If we want to print the initial tweet, and just the replies to that tweet, 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 in 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 in 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 in 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
Print the text of the comment
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 tweet and see it work
print_comment_and_replies(comment_about_exam)
That last exam in 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 in 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?