Trees and Priority Queues

1. You are implementing a tree and decide you want to store the depth of every node in the node itself. The only problem is that when you insert nodes in the tree, every node below the inserted node needs to change its depth. Write a function that increases the value of depth in a node and all nodes below it

         def inc-depth(node):
           node.depth +=1
           for child in node.children:
             inc-depth(child)
   

2. For the two trees, Perform a preorder and a postorder traversal. For the binary tree, also perform an inorder traversal.
   a)
   

         Pre: A B E F C G D H I J
         Post: E F B G C H I J D A
       

   b)

         Pre: A B D H I E C F J K G
         Post: H I D E B J K F G C A
         In: H D I B E A J F K C G
       

3. What is the main drawback of implementing a tree with an array?

   If there any spots in the tree where a node doesn't have a child, that results in a gap in the array where there is no data stored. This gap grows exponentially as the tree gets taller, wasting a lot of space.

4. What is the output of the following code:

         pq = PriorityQueue()
         pq.insert('A', 4)
         pq.insert('B', 3)
         pq.insert('C', 5)
         print(pq.removeMin())
         pq.insert('D', 2)
         pq.insert('E', 1)
         print( pq.removeMin())
         pq.insert('F', 3)
         pq.insert('G', 6)
         print(pq.removeMin())  
         print(pq.removeMin())  
         pq.insert('H', 7)
         pq.insert('I', 0)
         print(pq.removeMin())  
         print(pq.removeMin())  
         print(pq.removeMin())  
       

         B E D F I A C
       

5. 15 items are inserted into a min priority queue with the following priorities: 100, 58, 95, 77, 67, 62, 35, 66, 49, 54, 42, 33, 39, 99, 15. .
   1. Draw the resultant min priority queue if it were implemented as an unsorted array.

      	  [ 100, 58, 95, 77, 67, 62, 35, 66, 49, 54, 42, 33, 39, 99, 15]
      	

   2. Draw the resultant min priority queue if it were implemented as a sorted array.

      	  [15, 33, 35, 39, 42, 49, 54, 58, 62, 66, 67, 77, 95, 99, 100]
      	

   3. Draw a min heap after 7 inserts.

      	  [35, 67, 58, 100, 77, 95, 62]
      	

      
      
   4. Draw the heap after all 15 inserts.

      	  [15, 42, 33, 66, 49, 39, 35, 100, 67, 77, 54, 95, 58, 99, 62]
      	

      
      
   5. Draw the heap after 8 removeMin()s

      	  [62, 66, 95, 67, 77, 100, 99]