- Why Use Binary Trees?
- Tree Terminology
- An Analogy
- How Do Binary Search Trees Work?
- Finding a Node
- Inserting a Node
- Traversing the Tree
- Finding Minimum and Maximum Key Values
- Deleting a Node
- The Efficiency of Binary Search Trees
- Trees Represented as Arrays
- Printing Trees
- Duplicate Keys
- The BinarySearchTreeTester.py Program
- The Huffman Code
- Summary
- Questions
- Experiments
- Programming Projects
This chapter is from the book
This chapter is from the book
This chapter is from the book
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.