Data Structures & Algorithms

Exam 2

Sample 3, 75 Minutes

Solutions

1. (a)

   We will use a static variable maxDifferenceSoFar to represent the maximum height difference detected so far.
   private static int maxDifferenceSoFar;
   
   Whenever we determine the height difference between the left and right subtrees of a new node, the absolute value of this difference is compared to maxDifferenceSoFar, and maxDifferenceSoFar updated if necessary. To implement a recursive strategy, we need to define a public and a private maxHeightDifference method. The public method is given below:
   

   public int maxHeightDifference()
   {
      maxDifferenceSoFar = 0;    // initialize static variable
      maxHeightDifference(root); // compute max height difference
      return maxDifferenceSoFar;
   }
   

   The private method that does the actual computation of the maximum height difference is given below. This method also returns the height of the tree whose root is t.

   
   private static int maxHeightDifference(MyBinaryTreeNode t)
   {// return height of t and update maxDifferenceSoFar
      if (t == null)
         return 0;  // height of empty tree
   
      // compute heights of left and right subtrees
      int heightLeft = maxHeightDifference(t.leftChild);
      int heightRight = maxHeightDifference(t.rightChild);
   
      // determine height difference and update masDifferenceSoFar
      int heightDifference = heightLeft - heightRight;
      maxDifferenceSoFar = Math.max(maxDifferenceSoFar,
                                Math.abs(heightDifference));
      
      // return height of subtree rooted at t
      return Math.max(heightLeft, heightRight) + 1;
   }
   
   

   (b)

   Each node of the binary tree is reached once and a constant amount of work is done at each node. Therefore, the complexity is O(n), where n is the number of nodes in the binary tree.

   
   
   
   
   
   
   

2. (a)

   The complete binary tree is given below:

                           20
                       /       \
                      /         \
                     15         12 
                   /   \       /   \
                  8    10     6     2
                 / \   /
                4  7  1
   

   This is a max heap because it is both a complete binary tree and a max tree.

   (b)

   The winner tree is:

                           g
                       /       \
                      /         \
                     b           g
                   /   \       /   \
                  b     c     f     g
                 / \   / \   / \   / \
                1  7  4  3  5  8  9   2
                a  b  c  d  e  f  g   h
   
   

   (c)

   The loser tree is:

                           g <--- overall winner
                           |
                           b
                       /       \
                      /         \
                     c           f
                   /   \       /   \
                  a     d     e     h
                 / \   / \   / \   / \
                1  7  4  3  5  8  9   2
                a  b  c  d  e  f  g   h
   
   

   
   

3. (a)

   Examine the level order output from left to right. In this order, subtree roots are seen before subtree descendants. So, the first element in level order, B, is the root of the binary tree. Also B comes between the left and right subtrees in inorder. So the inorder output of the left subtree is A and CDEFGHIJ is the inorder output of the right subtree. The next element in level order A is the root of whichever subtree it is in. Using this information and what we have already learnt from the inorder sequence, we see that A is the root of the left subtree. Proceeding in this way we can construct the entire binary tree. The unique binary tree from which the given inorder and level order outputs came is:

                           B
                          / \
                         /   \
                        A     I
                            /    \
                           D      J
                          / \     
                         C   F   
                            / \ 
                           E   H
                              / 
                             G
   

   (b)

   When the max element is removed, we get the following 2 max leftist trees:
   
   

                 55    48
                /  \  /  \
              50  52  20  30
              /            
             40          
   

   These trees are melded by following rightmost paths. First, the right subtree of 55 is melded with the tree whose root is 48. The result is:

                        52
                        /  
                       48 
                      / \
                     20  32
                                   
   

   This new tree becomes the right subtree of 55. The subtrees of 55 are not swapped, as the tree already satisfies the leftist tree properties.

                        55
                       /  \
                      50  52
                      /   /  
                     40  48 
                        / \
                       20  32
                                   
   

   (c)

   Balance factors are shown in place of key values.

                    -1                        
                   /  \                      
                  /    \                   
                  1    -1                
                /  \  /  \              
               0   0  1   2           
              / \     /   /
             0   0   0    1            
                         /
                        0
   

   The given binary search tree is not an AVL search tree because it has a node whose balance factor is 2.