CODEWITHSUNDEEP
pythonalgorithmdata-structurestree
Arnav Luhadiya
Arnav Luhadiya

Reputation: 71

Minimum Element in Binary Search Tree

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?

Upvotes: 0

Views: 1205

Answers (2)

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

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)

Upvotes: 0

Paul Cornelius
Paul Cornelius

Reputation: 10946

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.

Upvotes: 1

Related Questions