-2 
# stack_depth is initialised to 0
def find_in_tree(node, find_condition, stack_depth):
    assert (stack_depth < max_stack_depth), 'Deeper than max depth'
    stack_depth += 1
    result = []
    if find_condition(node):
        result += [node]
    for child_node in node.children:
        result.extend(find_in_tree(child_node, find_condition, stack_depth))
    return result

I need help understanding this piece of code. The question i want to answer is

The Python function above searches the contents of a balanced binary tree. If an upper limit of 1,000,000 nodes is assumed what should the max_stack_depth constant be set to?

From what I understand, this is a trick question. If you think about it, stack_depth is incremented every time the find_in_tree() function is called in the recursion. And we are trying to find a particular node in the tree. And in our case we are accessing every single node every time even if we find the correct node. Because there is no return condition when stops the algorithm when the correct node is found. Hence, max_stack_depth should 1,000,000?

Can someone please try to explain me their thought process.

Improve this question
5
  • 1
    Only about 20. Hint: Try to prove that the value of stack_depth is equal to the distance between node and the root. Commented Mar 21, 2018 at 12:47
  • I understand how u get 19. You pretty much go 1+2+4+8+16......... until you reach 1,000,000. But are we not calling find_in_tree() for EVERY SINGLE NODE in the tree and incrementing stack_depth? Commented Mar 21, 2018 at 12:50
  • You can see the answers below which explains your mistake (local variable) Commented Mar 21, 2018 at 12:51
  • Uh... don't shout (write in capital case) please. Commented Mar 21, 2018 at 12:52
  • Sorry I wasnt shouting, I just placed it there to highlight it. Commented Mar 21, 2018 at 12:57

2 Answers 2

Reset to default
1

The key thing to notice is that stack_depth is passed down to each recursive call of the function. If it's a balanced binary tree then each call to find_in_tree will pass the same stack_depth value to up to two children. Just keep in mind that the reference to stack_depth is not shared between subsequent calls to find_in_tree. They will have their own version of stack_depth initialized to the value of the parent call.

This should be enough information to figure out what the value should be before the assert fires.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you very much. I understand that.
Now another question, If the assumptions (upper limit of 1,000,000 nodes) regarding the trees are wrong, what is at risk of occurring? Will the program just crash because the program will try access out of bound memory?
You will likely get a RecursionError, which is thrown when you reach the maximum recursion depth. You can try this yourself with a simple program like: def recur(): recur(); recur()
If you really need it to run for more than the recursion limit you can also try raising the recursion limit. However if you really need it to run at a higher recursion limit (which for a balanced binary search tree would be an enormous tree), you are probably better off switching to a different solution.
Thanks so much for your help.
|
1

If you look at when stack_depth increments then it looks like we will increment every time we access a node. And in our case we are accessing every single node every time. Because there is no return condition when stops the algorithm when the correct node is found.

This is incorrect. While a stack_depth variable is incremented for every node examined, it's not the same stack_depth variable. stack_depth is a local within the function. When find_in_tree recurses and the recursive call increments stack_depth this does not change the value of stack_depth in the caller.

stack_depth is measuring the level of recursion that takes place as this function runs to completion. The maximum value it takes on will be the maximum depth of the tree you're inspecting.

That said, if all you know is that you have a million nodes, you still need to step max_stack_depth to a million to guarantee the assertion doesn't fail because you don't know what shape the tree has. It could be that every node has exactly one child. In this case, you would need to recurse about a million times (maybe 999,999 times depending on how you count) to visit every node.

Of course, Python will stop you long before you get there.

Fortunately, you also know the tree is balanced. This means many nodes have two children. This tells you the maximum depth you will find should be close to the log base 2 of the number of nodes.

Improve this answer

5 Comments

"balanced". (4 more to go)
yea thanks, adjusted.
Thanks for the clear answer :)
Now another question, If the assumptions (upper limit of 1,000,000 nodes) regarding the trees are wrong, what is at risk of occurring? Will the program just crash because the program will try access out of bound memory?
Why did you post this exact question twice?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.