You will eventually want to search the tree to determine if it contains a given key or to locate a specific element. If the binary search tree conatins a target key, then there will be a unique path from the root to the node containing that key. However how do we know which path to take?

Since the root node provides the single access point into any binary tree, our search must begin there. The target value is compared to the key in the root node.

if the root contains the target value, our search is over with a successful result.

elif the target is not in the root, we must decide which of two possible paths to take. From the definition of the binary search tree, we know the key in the root node is larger than the keys in its left subtree and smaller than the keys in its right subtree. Thus, if the target is less than the root’s key, we move left and we move right if it’s greater. We repeat the comparison on the root node of the subtree and take the appropriate path. This process is repeated until target is located or we encounter a null child link.

def _search(self, subtree, target):
		
		# base case 1
		if subtree == None:
			return None
		
		# target is left of the subtree root
		elif target < subtree.key:
			return self._search(subtree.left, target)
		
		# target is right of the subtree root
		elif target > subtree.key:
			return self._search(subtree.right, target)
		
		# base case 2
		# the target is contained in the current node
		# returns a reference to the current node containing that key
		else:
			return subtree

The _search() helper method, recursively navigates a binary search tree to find the node containing the target key. The method has two base cases: the target is contained in the current node or a null child link is encountered. When a base case is reached, the method returns either a reference to the node containing the key or None, back through all of the recursive calls found in the tree. The recursive call is made by passing the link to either the left or right subtree depending on the relationship between the target and the key in the current node.