min

Given the definition of a the binary search tree, we know the minimum value is either in the root or in a node to its left. However how do we know if the root is the smallest value and not somewhere in its left subtree? We could compare the root to its left child, but if you think about it there is no need to compare individual keys, this is because of the inherit relationship between the keys.

If the root node contains keys in its left subtree, then it cannot possible contain the minimum key value since all of the keys to the left of the root by definition are smaller than the root.

If the root node does not have a left child, then it’s the smallest key value, since all of the keys to the right are larger than the root.

If we apply the same logic to the left child of the root node (assuming self.root.left ≠ None) to that node’s left child and so on, we will eventually find the minimum key value.

The minimum key value will be found in a node that is either a left or an interior node with no left child.

def _min(self, subtree):
		if subtree == None:
			return None
		elif subtree.left == None:
			return subtree
		else:
			return (self._min(subtree.left))

def _max(self, subtree):
		if subtree == None:
			return None
		elif subtree.right == None:
			return subtree
		else:
			return (self._max(subtree.right))