Chapter 15

These are the solutions to the exercises found in the section .

1. The tree should look like this. Note that it’s not well balanced, as the root node only has a right subtree and no left one:

   

2. Search within a balanced binary search tree takes a maximum of about log(N) steps. So, if N is 1,000, search should take a maximum of about 10 steps.

3. The greatest value within a binary search tree will always be the bottom rightmost node. We can find it by recursively following each node’s right child until we hit the bottom:

   ​	​def​ ​max​(node):
   ​	​if​ node.right_child:
   ​	​return​ max(node.right_child)
   ​	​else​:
   ​	​return​ node.value

4. Here’s the order for preorder traversal:

   

5. Here is the order for postorder traversal: