Exam 2

Sample 1, 50 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 function. The public function can be defined inline as below:
```
BinaryTree<T>& SwapChildren()
      {SwapChildren(root); return *this;}
```
The private function that does the actual swapping of children by performing a postorder traversal is given below. The relevant files are bbinary.*.
```
template<class T>
void BinaryTree<T>::SwapChildren(BinaryTreeNode<T> * &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) {// t is not null
           SwapChildren(t->LeftChild);
           SwapChildren(t->RightChild);
           Swap(t->LeftChild, t->RightChild);
          }
}
```
(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 Theta(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 and in the files minheap.*.


template<class T>
MinHeap<T>& MinHeap<T>::Insert(const T& x)
{// Insert x into the min heap.
   if (CurrentSize == MaxSize)
      throw NoMem(); // no space

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

   return *this;
}

(b): Since a heap is a complete binary tree, the height of a min heap that has CurrentSize = n elements is Theta(log n). The insert algorithm 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
```

BACK