Course Home | Course Policies | Homework | Lab Open Hours | Programming | Labs | Schedule & Lecture Notes

## Homework Assignment 4

### Problems to be Submitted (30 points)

1. (8 points)

Assume that we start with an initially empty heap, and that items are inserted with the following sequence of integer keys:

insert(12), insert(7), insert(14), insert(5), insert(20), insert(11), insert(6), insert(18), insert(8), insert(3), insert(17), insert(13), insert(4), insert(9).
Using Figure 7.3 as a guide for style, draw the heap which results at the very end of the last operation.

Note: for this problem we are not requiring you to show any of the work along the way, though you may if you wish. Please do be careful to follow the exact sequence given and to double-check your work.

2. (2 points)

In class, we wrote an array based implementation of heaps. Please draw the contents of an array which represents the tree T you gave in your answer to Problem A.

3. (5 points)

Exercise R-7.15 on page 358 of the text.

4. (5 points)

For the tree in Figure 6.6 (on page 259), what order will nodes be visited during a postorder traversal?

5. (5 points)

Draw a (proper) binary tree T such that simultaneously,

• each node of T stores a single character
• a preorder traversal of T yields BIGZANYCOMPUTER
• an inorder traversal of T yields GIAZNBCYPMTUEOR
6. (5 points)

Insert, into an initially empty binary search tree, items with the following keys (in this order): 33, 40, 24, 58, 49, 20, 63, 25, 11, 13. Draw the final tree after that order of insertions. (Again, you may wish to show your work along the way.)