Post Lab 27

Tracing Trees

Draw the state of the tree at the end of each of these blocks of code. If there is an error in the code, please write Error.

1.       my_tree = Tree()
   
         for i in range(5):
             my_tree.insert(i)
       

2.       my_tree = Tree()
   
         for i in range(4, -1, -1):
             my_tree.insert(i)
   
         for i in range(5, 10):
             my_tree.insert(i)
   
       

3.       my_tree = Tree()
         left_overs = []
         for i in range(10):
             if i % 2 == 0:
                 my_tree.insert(i)
             else:
                 left_overs.append(i)
   
         for item in left_overs:
             my_tree.insert(item)
       

4.       my_tree = Tree()
         elements = list(range(10))
   
         for i in range(5):
             my_tree.insert(elements[i])
             my_tree.insert(elements[len(elements) - i])
   
       

5.       my_tree = Tree()
         elements = list(range(10))
         
         def insert_rec(a_list, tree):
             mid = len(a_list) // 2
   
             tree.insert(a_list[mid])
             insert_rec(a_list[:mid], tree)
             insert_rec(a_list[mid:], tree)
   
         insert_rec(elements, my_tree)
       

6.       my_tree = Tree()
         elements = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
         
         def insert_rec(a_list, tree):
             mid = len(a_list) // 2
   
             tree.insert(a_list[mid])
             insert_rec(a_list[:mid], tree)
             insert_rec(a_list[mid:], tree)
   
         insert_rec(elements, my_tree)
       

Submission

Bring this completed worksheet with you to the beginning of class on Friday.

Post labs are to be done individually. Sharing files between students is not allowed. Doing so is an Academic Integrity violation, and will be treated as such.