Data Structures & Algorithms

Exam 2, Sample 1

75 Minutes

Solutions

(a)
To perform the operation, we can do a postorder traversal of the binary tree. During the visit step, we exachange the left and right children of the node being visited. To implement this strategy we need to define a public and a private swapTree method. The public method can be defined as below:
```
public void swapChildren()
   {swapChildren(root);}
```
The private method is a class (i.e., static) method that does the actual swapping of children by performing a postorder traversal. The code is given below.
```
private static void swapChildren(BinaryTreeNode t)
{// Swap the children of every node in the subtree t.
 // Do a postorder traversal; swap left and right child
 // pointers in the visit step.
   if (t != null)
   {
      // swap in the left subtree
      swapChildren(t.leftChild);

      // swap in the right subtree
      swapChildren(t.rightChild);

      // swap children of t
      BinaryTreeNode temp = t.rightChild;
      t.rightChild = t.leftChild;
      t.leftChild = temp;
   }
}
```
(b)
Each node of the binary tree is visited 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.

(a): The strategy is the same as for a max heap. The code is given below.


/** put theElement into the heap */
public void put(Comparable theElement)
{
   // increase array size if necessary
   if (size == heap.length - 1)
      heap = (Comparable []) ChangeArraySize.changeSize1D
                                 (heap, 2 * heap.length);

   // find place for theElement
   // i starts at new leaf and moves up tree
   int i = ++size;
   while (i != 1 && heap[i / 2].greaterThan(theElement))
   {
      // cannot put theElement in heap[i]
      heap[i] = heap[i / 2]; // move element down
      i /= 2;                // move to parent
   }

   heap[i] = theElement;
}

(b): Since a heap is a complete binary tree, the height of a min heap that has size = n elements is O(log n). The put method spends constant time at a level and goes through at most as many levels as the height of the min heap. So the complexity is O(log n).

(a)
Since S _n = 1 + alpha/2 <= 4, alpha <= 6
Also, since U _n = (1 + alpha)/2 <= 2, alpha <= 3.
So alpha <= min{6, 3} = 3.
Hence n/b = alpha <= 3 and so b >= n/3 = 81/3 = 27.

When division is used, the number of buckets equals the divisor D. So D >= 27. Also since D should be a prime number or should have no prime divisors less than 20, we choose D = 29, which is a prime number.

(b)
Following path compaction, all nodes on the original path from the find element e to the root are children of the original root.

(c)
Examine the postorder output from right to left. In this order, the first element F is the root of the binary tree. Also F comes between the left and right subtree in inorder. So ABCDE is the inorder output of the left subtree and GHIJ is the inorder output of the right subtree. The next element in postorder I is the root of the right subtree unless the right subtree is empty (in which case it is the root of the left subtree). Using this information and what we have already learnt from the inorder sequence, we see that I is the root of the right subtree and GH are in the left subtree of I and J in its right subtree. Proceeding in this way we can construct the entire binary tree. The unique binary tree from which the given inorder and postorder outputs came is:
```
                    F
               /        \
             E             I
          /             /    \
        A             G        J
         \             \
           C             H
         /  \
        B    D
```