CMSC 10700 Spring 2004
Sharon Salveter

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 binary tree.
• Then come N numbers, forming the inorder traversal of the binary tree.
• Finally come N numbers, the preorder traversal of the binary 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, which will be available on the website on Tuesday 4 May.

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?