Data Structures & Algorithms

Exam 2, Sample 2

75 Minutes

Solutions

1. (a)

   To implement a recursive strategy, we need to define a public and a private elementAtLevel method. The public method can be defined as below:
   

   /** @return an element at level theLevel */
   public Object elementAtLevel(int theLevel)
      {return elementAtLevel(root, theLevel);}
   

   The private method that does the actual search for an element at the desired level.

   
   /** @return an element at level theLevel of subtree rooted at t */
   private static Object elementAtLevel(BinaryTreeNode t, int theLevel)
   {
      if (t == null)
         // empty tree, no element at level theLevel
         return null;
   
      if (theLevel == 1)
         // t is at level 1
         return t.element;
   
      // search for desired element in left subtree
      Object x = elementAtLevel(t.leftChild, theLevel - 1);
      if (x != null)
         // found an element at level theLevel
         return x;
   
      // return desired element from right subtree
      return elementAtLevel(t.rightChild, theLevel - 1);
   }
   
   

   (b)

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

   
   
   
   
   

2. (a)

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

   (b)

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

   
   

3. (a)

   Following path halving, every other node on the original path from the find element e to the root points to its original grandparent.
   
   

   (b)

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

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

   
   
   

   (c)

                                70
                             /       \
                            /         \
                           /           \
                          60           61
                         /  \          / \
                        /    \        /   \
                       55    54      58   59
                      /  \  /  \     /
                     50  52 48 53   56
                     /     / \
                    40    20 45
                             /
                            30