# FAQ: Recursion vs. Iteration - Coding Throwdown - How Deep Is Your Tree?

This community-built FAQ covers the “How Deep Is Your Tree?” exercise from the lesson “Recursion vs. Iteration - Coding Throwdown”.

Paths and Courses
This exercise can be found in the following Codecademy content:

## FAQs on the exercise How Deep Is Your Tree?

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply ( ) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

## Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply ( ) below!

Agree with a comment or answer? Like ( ) to up-vote the contribution!

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Can someone please explain how the recursive solution to this works. I’m not understanding how the recursive step moves the function towards the base case.

1 Like
``````if not tree: return 0
``````

Eventually there won’t be any child nodes.

2 Likes

got that, I guess I’m confused as to how the function is traversing the tree from top to bottom?

1 Like

The depth keeps increasing on either the left or right with each recursion.

https://cscircles.cemc.uwaterloo.ca/visualize

Paste in and click ‘Visualize Execution’…

``````def depth(tree):
if not tree:
return 0

left_depth = depth(tree["left_child"])
right_depth = depth(tree["right_child"])

if left_depth > right_depth:
return left_depth + 1
else:
return right_depth + 1

# HELPER FUNCTION TO BUILD TREES
def build_bst(my_list):
if len(my_list) == 0:
return None

mid_idx = len(my_list) // 2
mid_val = my_list[mid_idx]

tree_node = {"data": mid_val}
tree_node["left_child"] = build_bst(my_list[ : mid_idx])
tree_node["right_child"] = build_bst(my_list[mid_idx + 1 : ])

return tree_node

# HELPER VARIABLES
tree_level_4 = build_bst([1, 2, 3, 4, 5])

# test cases
print(depth(tree_level_4) == 4)
``````
12 Likes

I copied and pasted the same iteration example into IDLE and I received an error.

Traceback (most recent call last):
File “C:/Users/notis/AppData/Local/Programs/Python/Python37-32/tree nodes.py”, line 33, in
if child[“left_child”]:
KeyError: ‘left_child’

Why does the code for the iteration work on here and not on IDLE (also does not work on Visual Studio).

1 Like

I think the iterative solution for the function requires checking if a key exists like so:

if “left_child” in child:
if “right_child” in child:

Upon making this change the code should execute correctly. Note that directly copying and pasting the iterative algorithm into Codecademy’s workspace, even with the corrections, will still throw an error, as the module seems to run background testing functions against your code, which the iterative example does not resolve against.

That Waterloo site seems a fantasitc resource. Thank you.

2 Likes

I used the .get() method with a default value of False to avoid a KeyError when the key doesn’t exist in the dictionary. I also printed the calls to the function to see the output in my terminal

if child.get(“left_child”, False):
queue.append(child[“left_child”])
if child.get(“right_child”, False):
queue.append(child[“right_child”])

`````` queue = [tree]
``````

Is this a list of the tree dictionary?

`````` level_count = len(queue)
``````

On the exercise, it is saying that `level_count = len(queue) ` will count the number of child nodes but what I understand is that len(queue) would return the number of element in the queue, in this case, is it supposed to return 1 because there is only one element in the list? Can someone explain it?

this is rather vague so it’s quite likely you and the exercise has different ideas about what that means

what they mean is that they want to process all trees that are in the queue at this moment

there can be other amounts of trees in that list

you could also do it this way:

``````queue = [tree]

while queue:
children = []
for t in queue:
...
children.append(someresult)
queue = children  # this is now the new queue
``````

There’s also a much nicer way of getting depth of a tree, use max on the depth of each child, unless there are no children in which case the depth is 1 (or 0, depending on perspective)

``````def depth(tree):
if no children: return 1
return 1 + max(depth(left), depth(right))
``````

(you’d have to get the edge cases (no children, missing 1 child) right, but that’s the general idea)

…uh. maybe that’s the point they’re making? but there’s another difference as well, one of them is depth first while the other is breadth first and you can do both with each of recursion/iteration, recursion is a jump with a built in stack so that you can get back later, iteration is jumping too, you’d just have to manage a stack of your own

1 Like

Thanks for your time and explanation.
I am getting some ideas now.

Can someone recommend me some easy exercises with recursion? Learning curve in here has been extremely steep and as I got first couple of exercises last 6 are impossible, waaaaaaay to hard so in order to learn recursion I need to find some exercises that will actually be possible and will actually teach me something (cannot learn from sth you don’t understand)

2 Likes

you are missing what this step is doing
'for child_count in range(0, level_count):
# loop through each child
child = queue.pop(0)
# add its children if they exist
if child[“left_child”]:
queue.append(child[“left_child”])
if child[“right_child”]:
queue.append(child[“right_child”])

in the for loop “child” refers to “tree” we know this because “queue.pop()” (pop return what it removes form the list)

therefore “child[“left child”]” and "child[“right child]” are accessing the dictionary stored in the variable tree and are checking if the key “left child” or “right child” is present.

if the child is present it will add it to the queue forming the queue to check the next level

level count is used to keep track of the number of times queue should be iterated through.

in the iteration every element is removed from the queue, and every elements children are added to the queue getting the number of iterations for iterating through the next level

i dont have a link to specific recursion problems but try out code wars.
they have gameified coding problems by having a leaderboard and difficulty levels for the problems.
once you solve a problem you can see other players solutions and discuss them.

choose an easier level, solve a problem by iteration, go back to that same problem and try to do it recursively.

its a great tool for learning a coding language.

1 Like

This is my solution whis is not as efficient:

``````def depth(tree):
if not tree["left_child"]:
return 1
if not tree["right_child"]:
return 1
return 1 + max(depth(tree["left_child"]), depth(tree["right_child"]))
``````
1 Like

Hi guys,
I have the following code, when testing it out, it seems to work, I’m able to find the additional “levels” however my levels variable doesn’t update and always returns 1, can you help as to figure out why?

``````def depth(tree):
level = 1
if tree['left_child'] == None:
print(f"all levels found, levels {level}")
return level + extra_levels
else:
print(f"found extra level, currently on levels {level}")
extra_levels += 1
depth(tree['left_child'])

``````

Can someone please explain me the Big -O of the recursion part of the algorithm, is it “2^N”, if so can you please explain it how , if not please explain the other answer.
Thanks 1 Like

In this algorithm, you will visit every node in the tree once. What is the runtime for iterating over every item?

First of all:
level_4 == 4 call returns False even using the optimal solution the exercise gives you in the end. As well as mtf’s example. (Awesome website by the way, I bookmarked it!)

Some explanation there would be great.

Secondly:

Following mtf’s guidance I had a look and I’m still stumped. Mainly I’m confused how left_depth and right_depth can be compared. How is left_depth bigger or smaller than right_depth?

In the runtime, it’ll recurse around until left_child is none, and then proceed to calling it on right_child. Cool, fine. But how is the program keeping track of how many times left_child was called vs. right child?

I’m really not following it. I get the concept of the call stack I just am failing to translate that into a real understanding of how this works.

The other exercises i either completed without help after some trial and error, or at least understood post hoc. This one? Confused!