how to use Binary tree search in Python

0 votes

# 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.

Sep 27, 2018 in Python by bug_seeker
• 14,960 points
40 views

1 answer to this question.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
0 votes
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.
answered Sep 27, 2018 by Priyaj
• 56,100 points

Related Questions In Python

0 votes
1 answer

How to use string.replace() in python 3.x

replace() is a method of <class 'str'> ...READ MORE

answered Aug 3, 2018 in Python by Priyaj
• 56,100 points
23 views
+1 vote
2 answers

How to use the pass statement in Python

In Python programming, pass is a null statement. The ...READ MORE

answered Apr 5 in Python by anonymous
26 views
0 votes
1 answer

How to use multiprocessing queue in Python?

This is a simple example of a ...READ MORE

answered Oct 25, 2018 in Python by SDeb
• 9,380 points
78 views
0 votes
1 answer

How to use HashMap in Python?

You can use Python dictionary it is a built-in type ...READ MORE

answered Oct 26, 2018 in Python by Priyaj
• 56,100 points
439 views
0 votes
1 answer

how can i count the items in a list?

suppose you have a list a = [0,1,2,3,4,5,6,7,8,9,10] now ...READ MORE

answered May 2 in Python by Mohammad
• 1,400 points
19 views
0 votes
2 answers

How to use threading in Python?

 Thread is the smallest unit of processing that ...READ MORE

answered Apr 6 in Python by anonymous
43 views
0 votes
1 answer

How to use “raise” keyword in Python

You can use it to raise errors ...READ MORE

answered Jul 30, 2018 in Python by Priyaj
• 56,100 points
15 views

© 2018 Brain4ce Education Solutions Pvt. Ltd. All rights Reserved.
"PMP®","PMI®", "PMI-ACP®" and "PMBOK®" are registered marks of the Project Management Institute, Inc. MongoDB®, Mongo and the leaf logo are the registered trademarks of MongoDB, Inc.