Binary Trees

This chapter is from the book

Data Structures & Algorithms in Python

Learn More Buy

This chapter is from the book

This chapter is from the book 

Data Structures & Algorithms in Python

Learn More Buy

Finding Minimum and Maximum Key Values

Incidentally, you should note how easy it is to find the minimum and maximum key values in a binary search tree. In fact, this process is so easy that we don’t include it as an option in the Visualization tool. Still, understanding how it works is important.

For the minimum, go to the left child of the root; then go to the left child of that child, and so on, until you come to a node that has no left child. This node is the minimum. Similarly, for the maximum, start at the root and follow the right child links until they end. That will be the maximum key in the tree, as shown in Figure 8-17.

FIGURE 8-17 Minimum and maximum key values of a binary search tree

Here’s some code that returns the minimum node’s data and key values:

   def minNode(self):              # Find and return node with minimum key
      if self.isEmpty():           # If the tree is empty, raise exception
         raise Exception("No minimum node in empty tree")
      node = self.__root           # Start at root
      while node.leftChild:        # While node has a left child,
         node = node.leftChild     # follow left child reference
      return (node.key, node.data) # return final node key and data

Finding the maximum is similar; just swap the right for the left child. You learn about an important use of finding the minimum value in the next section about deleting nodes.