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!
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.
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).
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.
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”])
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
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)
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.
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"]))
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
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!
) below.
) to up-vote the contribution!