Need help with searching a binary search tree

0 votes
Need help with searching a python binary search tree

[code]
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
[/code]

I really need some help understanding this particular piuece of code

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.So the worst case would be when we have to search through all the nodes in the tree before we find it. Hence, max_stack_depth should 1,000,000?

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.

Can someone please try to explain me their thought process.
Apr 17, 2018 in Python by aryya
• 7,460 points
851 views

1 answer to this question.

0 votes
Instead of multiplying the number of nodes on each layer, you have to add them. For example, the number of nodes in the first four layers is 1+2+4+8=15, not 1*2*4*8=64.

                #                      1
      #                   #          + 2
  #       #           #       #      + 4
#   #   #   #       #   #   #   #    + 8 = 15
In general, the number of nodes in the first n layers is 2**(n+1)-1. You can use logarithms to get the correct power and get the floor of that number. If you want fewer that that number, you would also have to subtract one from the power.

>>> math.floor(math.log(1000000, 2))
19
>>> sum(2**i for i in range(1, 20))
1048574
Concerning your edit: Yes, stack_depth is incremented with each node, but you are incrementing a local variable. The increment will carry to the child nodes (passed as a parameter) but not to the siblings, i.e. all the nodes at level n will be called with stack_depth == n-1 (assuming it started as 0 on the first level). Thus, max_stack_depth should be 19 (or 20 if it starts with 1) to visit the ~1,000,000 nodes in the first 19 levels of the tree.
answered Apr 17, 2018 by anonymous

Related Questions In Python

0 votes
1 answer

Need help with the output of a code snippet.

If you write x.insert(2,3) and then print x ...READ MORE

answered Jun 23, 2020 in Python by Viraj Doshi
3,381 views
0 votes
1 answer

Need help with Tkinter window formatting using Python

Tkininter comes with the columnspan argument to span the labels ...READ MORE

answered Sep 7, 2018 in Python by aryya
• 7,460 points
878 views
0 votes
1 answer

how to use Binary tree search in Python

The key thing to notice is that ...READ MORE

answered Sep 27, 2018 in Python by Priyaj
• 58,020 points
1,044 views
+1 vote
1 answer

Need some help with Python memory leaks

As far as best practices, keep an ...READ MORE

answered Nov 26, 2018 in Python by Nymeria
• 3,560 points
968 views
0 votes
1 answer

Need help extracting a schema to make use for an avro file in Python

Hi, nice question. So what I daily use ...READ MORE

answered Jan 10, 2019 in Python by Nymeria
• 3,560 points
4,963 views
–1 vote
1 answer
0 votes
1 answer

Need help with Python Text-to-Speech usage

Hi. Just before I begin my answer I ...READ MORE

answered Jan 16, 2019 in Python by Nymeria
• 3,560 points
1,025 views
0 votes
1 answer
0 votes
1 answer

Need help writing a dataframe into a csv with the help of a loop

Using the following logic you can arrive ...READ MORE

answered Apr 17, 2018 in Python by anonymous
3,368 views
0 votes
1 answer

How can I write nested dictionaries to a csv file?

You can use the pandas library to ...READ MORE

answered Apr 17, 2018 in Python by anonymous
1,167 views
webinar REGISTER FOR FREE WEBINAR X
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP