Python Binary Tree Min value function

Question

I am trying to work on Binary tree in python and trying to get Min value in BST. But I am facing a small problem.

def MinVal(self):
    if self.root == None:
       return None
    else:
       return self._MinVal(self.root)

def _MinVal(self, node):
    if node.left != None:
       self._MinVal(node.left)
    else:
       res = node.data
       print(res)
       return res

When I print the res variable I am getting my answer but in the next statement when I return it, the value is shown None. Why is it so ?

in your if block just change self._MinVal(node.left) to return self._MinVal(node.left) — Courage
– Courage, Commented Jun 28, 2017 at 6:21

Pang · Accepted Answer · 2017-09-09 01:57:25Z

1

UPDATE: To keep the recursive approach and fix the existing code, simply change line 3,
ie. self._MinVal(node.left) to return self._MinVal(node.left).

The addition of the return keyword there will ensure that the return value will bubble up from the bottom of the recursion stack.

def _MinVal(self, node):
    if node.left != None:
       self._MinVal(node.left)
    else:
       res = node.data
       print(res)
       return res

When you print(res) you get the last traversed node to the left, which is your correct answer. However, when you return res, you are returning the value to the previous function call in the recursive stack. Which means that your correct answer is returned to the function call execution at the previous node, where you have no return value. You are not passing your found value back up the stack, which is why the topmost instance returns None.

Try this, and it should work:

   #Pass root node to this function 
   def minValue(node):
    current = node

    # loop down to find the lefmost leaf
    while(current.left is not None):
        current = current.left

    return current.data

This function should do what you need, fairly smoothly.

edited Sep 9, 2017 at 1:57

Pang

10.2k146 gold badges87 silver badges126 bronze badges

answered Jun 28, 2017 at 6:27

Hriddhi Dey

131 silver badge5 bronze badges

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

2 Comments

TanvirDuggal Over a year ago

I already use the while statement to get min value, I want to get my hands over recursion so was practicing that. Can you tell me the sol with recursion?

Hriddhi Dey Over a year ago

Sure thing! On line 3 of your code, replace self._MinVal(node.left) with return self._MinVal(node.left). The addition of return there will bubble up the value you return from the bottom of the recursion stack, right to the top.

Collectives™ on Stack Overflow

Python Binary Tree Min value function

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related