Can I be helped in knowing my mistake in the insertion and searching operations of a BST?

Question

I am implementing a BST in Python. I have written the functions for inserting data and searching for it in a BST. The problem is, I have tried many times to find out what mistake I am making, but I haven't been able to do it correct. I request for some help. Please help me.

class Node:

    def __init__(self, data):
        self.data = data
        self.left_ptr = None
        self.right_ptr = None

class BinarySearchTree:

    def __init__(self):
        self.ptr_to_root = None


    def insert(self, data):
        '''
        This feature/function helps the users to insert data into a Binary 
        Search Tree.
        '''
        # To insert, the first thing we have to do is
        # creating a node :-
        node = Node(data)
        
        # We create a temperory pointer as we
        # won't move ptr_to_root.
        temp_ptr = self.ptr_to_root

        # CASE 1 > If ptr_to_root is None i.e. If BST
        # is empty :
        if temp_ptr == None:
            temp_ptr = node
        

        # CASE 2 > If BST is not empty already : 
        while temp_ptr != None:
             
            # Below is the pointer which will remain behind
            # temp_ptr by one step.
            r = temp_ptr
            
            # If we already have the data present in BST, we
            # cannot re-enter it. Hence, we simply exit the 
            # function.
            if data == temp_ptr.data:
                return
            
            # If the data is having lesser value then temp_ptr's data, 
            # then we move the temp_ptr to its left, or else the right.
            if data < temp_ptr.data:
                temp_ptr = temp_ptr.left_ptr
            else:
                temp_ptr = temp_ptr.right_ptr
        
        # r is the tail pointer, which follows the temp_ptr. 
        # Eventually, we will compare if the value that we wanrt to insert
        # is less or more then r.data, and accordingly insert the data desired.
        if data < r.data:
            r.left_ptr = node
        else:
            r.right_ptr = node

    

    def search(self, data):
        
        # If the BST is empty, then we do not 
        # have the element present in the BST for sure:
        temp_ptr = self.ptr_to_root
        
        # If BST is empty, then :
        if temp_ptr == None:
            return None

        
        # If BST is not empty, we may or may not be 
        # finding the element in the tree :
        while temp_ptr != None:

            if data == temp_ptr.data:
                return temp_ptr
            
            elif data < temp_ptr.data:
                temp_ptr = temp_ptr.left_ptr
            
            else:
                temp_ptr = temp_ptr.right_ptr
        
        # If the element is not present in BST :
        return None

When I run the above code for inserting an element and then searching for it; It returns 'None' even though I search for an element that I have inserted. Please Help!

Answer 1

Your problem is actually very simple, as a few minutes with a debugger would have shown you. You never create a root node. When you try to insert something into an empty tree, you set up the node, but you don't save it, so the tree is ALWAYS empty. Change this:

        # CASE 1 > If ptr_to_root is None i.e. If BST
        # is empty :
        if temp_ptr == None:
            temp_ptr = node
            self.ptr_to_root = node    # <<< add this line

and it all works.