educative.io

Searching in BST

Courses
,
#1

‘’’
def find(self, data):

    node = self.root

    a = self.ins(node,data)

    return a



def ins(self,node,data):

        if node == None:

            return

        if node.data == data:

            return True

        if data < node.data:

            if node.left == None:

                return False

            else:

                self.ins(node.left,data)

        if data > node.data:

            if node.right == None:

                return False

            else:

                self.ins(node.right,data)

‘’’
I cannnot figure out what is wrong with this code in searching for a node in BST. Tried everything and made sure there is no mistake in calling self or functional fault but still having nightmares solving it

Type your question above this line.

Course: https://www.educative.io/collection/10370001/5474278013140992
Lesson: https://www.educative.io/collection/page/10370001/5474278013140992/5348074945773568

#2

Hi @Mohammad_Alim. As you have written a recursive function that has boolean type. Every function call should return something to the previous function through which it was called. In your case, if an element is found, then True is returned but True is returned only from the last call of the function, and the function which called this function does not return anything, so this function reaches the end of the function, and None is returned.

Example:

        4
       /  \
     2      6
    / \    / \
   1   3  5   7

Note: Please ignore the colors. It is due to some formatting.

If we want to find 7, then there will be 3 function calls:

ins(self,node,data)  // node.data=4
ins(self,node,data)  // node.data=6
ins(self,node,data)  // node.data=7

ins(self,node,data) → ins(self,node,data) → ins(self,node,data)

According to your function, the value that we want to find will be founded on the 3rd call, and this 3rd function will return True but as you can see, this returned value from the 3rd function will not be used/returned by the 2nd function, so the execution of the 2nd function will end and it will return None. The same will be the case with the first function.

← ins(self,node,data) ← ins(self,node,data) ← ins(self,node,data)
← None ← None ← True

def ins(self,node,data):

        if node == None:

            return False

        if node.data == data:

            return True

        if data < node.data:

            if node.left == None:

                return False

            else:

                return self.ins(node.left,data)

        if data > node.data:

            if node.right == None:

                return False

            else:

                return self.ins(node.right,data)

Now, if we just add return before the function calls, then each function will return True or False to the previous function accordingly.

← ins(self,node,data) ← ins(self,node,data) ← ins(self,node,data)
← True ← True ← True

I hope this helps.

Happy Learning :smiley: