HW #7

For this assignment you will use Blackboard to submit a .py file containing an updated version of binary_tree.py from in-class activity #6. Your code should conform to the CS240 Coding Standards. Don't forget to include an honor code statement in your submission.

1. Complete Exercise #2 from in-class activity #6. (5pts)
2. Complete Exercise #3 from in-class activity #6. (5pts)

3. We have concluded that a binary tree with n nodes must have a height of at least ⌊ log₂n ⌋ + 1. It would be valuable to know the height of a typical binary tree with n nodes.

   It is possible to approach this question analytically, but for this exercise you will run some experiments to determine the approximate average height by randomly generating trees using the randomAdd method.

   Write a function named heightExperiment that takes no arguments. This function should create 100 randomly generated trees (using the randomAdd method) for increasing values of n, and should calculate the average height at each size. Your function should test power-of-two tree sizes from 2 to 2048. You function should have no return value, but should print out a table of experimental results formatted as follows:

   # Nodes    Average Height
   2          2.0 
   4          ???  
   8          ???  
   16         ???  
   32         ???  
   64         ???  
   128        ???  
   256        ???  
   512        ???  
   1024       ???  
   2048       ???  
   

   Where the question marks will be replaced by average height values. Both columns should be left justified.

4. Based on your results from the previous question, what big-O class does the average tree height appear to fall into? You can include your answer in the docstring of your method.