Minimum Element in Binary Search Tree

Question

Given a Binary Search Tree. The task is to find the minimum element in this given BST.

Example 1:

Input:
           5
         /    \
        4      6
       /        \
      3          7
     /
    1
Output: 1

Example 2:

Input:
             9
              \
               10
                \
                 11
Output: 9

Your Task: The task is to complete the function minValue() which takes root as the argument and returns the minimum element of BST. If the tree is empty, there is no minimum element, so return -1 in that case.

My Code:

def minValue(root):
   if root is None:
       return -1
   elif root.left is None:
       return root.data
   else:
       minValue(root.left)

This code is giving me the output None with every testcase whereas if I change my minValue(root.left) in the else condition to return minValue(root.left), I'm getting correct answer. Can anyone tell me the reason as to why this is happening?

Without the return statement, you toss the child's solution into the void. — ggorlen, Oct 28 '20 at 06:24
Not sure how. If the left child has the minimum value and you don't return it, it's gone forever. Consider `def add(a, b): return a + b` and `def add(a, b): a + b`. Will the second one do anything? Same problem here. — ggorlen, Oct 28 '20 at 06:34
Does this answer your question? [Why does my recursive function return None?](https://stackoverflow.com/questions/17778372/why-does-my-recursive-function-return-none) — Stef, Oct 28 '20 at 11:35

score 1 · Accepted Answer · answered Oct 28 '20 at 06:32

Every Python function returns something. If the function exits without a return then the returned value is None. Your code returns -1 if the first if statement is true. It returns root.data if the elif is true. Otherwise it returns None, since the else branch is taken and that returns nothing. It calls minValue but that doesn't actually do anything because you don't return anything there. After the function finishes the code just falls through to the end - and therefore Python returns None.

score 0 · Answer 2 · answered Oct 28 '20 at 06:39

You haven't added a return statement in the second case, hence the output shows None as nothing was actually returned. Just change it to

def minValue(root):
   if root is None:
       return -1
   elif root.left is None:
       return root.data
   else:
       return minValue(root.left)

Minimum Element in Binary Search Tree

2 Answers2