Balanced binary tree 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.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.

Sep 12, 2018 in Python by bug_seeker
• 14,970 points
35 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

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 Sep 12, 2018 by Priyaj
• 56,120 points

Related Questions In Python

0 votes
1 answer

Need help with searching a binary search tree

Instead of multiplying the number of nodes ...READ MORE

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

Binary numbers in python

>>> 0b1011 11 READ MORE

answered Jun 6, 2018 in Python by Hamartia's Mask
• 1,580 points
11 views
0 votes
1 answer

How do you express binary literals in Python?

For reference—future Python possibilities: Starting with Python 2.6 you ...READ MORE

answered Aug 14, 2018 in Python by ariaholic
• 7,320 points
74 views
+1 vote
1 answer

How do you express binary literals in Python?

Starting with Python 2.6 you can express ...READ MORE

answered Aug 28, 2018 in Python by Priyaj
• 56,120 points
82 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
20 views
0 votes
1 answer

Balanced binary tree python

Instead of multiplying the number of nodes ...READ MORE

answered Sep 24, 2018 in Python by Priyaj
• 56,120 points
13 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
• 56,120 points
41 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.