Post Lab 26

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):
             if len(a_list) > 0:
                 mid = len(a_list) // 2
   
                 tree.insert(a_list[mid])
                 insert_rec(a_list[:mid], tree)
                 insert_rec(a_list[mid + 1:], 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):
             if len(a_list) > 0:
                 mid = len(a_list) // 2
   
                 tree.insert(a_list[mid])
                 insert_rec(a_list[:mid], tree)
                 insert_rec(a_list[mid + 1:], tree)
   
         insert_rec(elements, my_tree)
       

Submission

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