CMSC 11700-01 Spring 2002
Sharon Salveter

Problems 1 is a pencil and paper exercise. Problem 2 is a programming exercise.

1. Prove that every strictly binary tree has 2 N₀-1 nodes, where N₀ is the number of nodes of degree 0 (that is, the leaves).

2. A specification for a binary tree with N > 0 nodes, labeled 1...N, is presented to you as follows:

• There are 2N + 1 numbers per record (line).
• The first is N itself, to tell you how many nodes there are in the tree.
• Then come N numbers, forming the inorder traversal of the tree.
• Finally come N numbers, the preorder traversal of the tree.

                        1
                       / \
                      /   \
                     2     4
                    /     / \
                   /     /   \
                  3     5     6

You are to write a program to read an arbitrary number of records, each representing the specification for a binary tree. For each tree specification, build the specified tree using dynamic allocation, and print information about the tree.

The information to print about each tree is:

• The postorder traversal of the tree. (3 2 5 6 4 1 in the example.)
• The height of the tree. (The example tree has height 2.)
• The frontier of the tree. (The leaves of the tree in inorder. 3 5 6 in the example.)
• The weight of the tree. (The weight of a tree is the sum of the weights of its nodes. The weight of a node is its value times one plus its level. That is, W = V * (L + 1). The weight of the example tree is 55 = 1*(1) + 2*(2+4) + 3(3+5+6). )

You must write a separate, recursive function to compute each piece of information. While it is possible to compute the required information without actually building the tree, you must build the tree. As usual, you should maintain your own freespace.

The program you turn in must run on the data I provide. It will be available on the website on Monday 29 April.

Don't forget input error checking. For example, there may not be enough numbers on the record, or the label of some node may not be in the range 1...N. In such cases, print an appropriate message and go on to process the next record.

Think about: Does every sequence of 2N+1 numbers represent a binary tree? For example, the sequence 5 2 1 4 3 5 1 5 2 4 3 has the correct number of values in the right range. Is there a 5-node binary tree with these inorder and preorder traversals?