Python Data Structures and Algorithms

Searching the tree

Since the insert method organizes data in a specific way, we will follow the same procedure to find the data. In this implementation, we will simply return the data if it was found or None if the data wasn't found:

    def search(self, data): 

We need to start searching at the very top, that is, at the root node:

        current = self.root_node         while True: 

We may have passed a leaf node, in which case the data doesn't exist in the tree and we return None to the client code:

            if current is None:                 return None 

We might also have found the data, in which case we return it:

            elif current.data is data:                 return data 

As per the rules for how data is stored in the BST, if the data we are searching for is less than that of the current ...