CSE 326, Winter 1999: Homework 3

Due 1/29/99

For all program or data structure design problems such as the two below you must provide pseudocode (see the manual)and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Staight pseudocode with no additional documentation is not enough.

1. (10 points) It is often handy to store a binary tree in a file. Assume each node in the binary tree contains a character string. Assume also that all operations you need on strings are provided. For example, you do not need to design algorithms to test if a string equals ".", to write a string into a file, or to read a string from a file. To create the file in preorder file format do a preorder traversal of the tree, when a node is visited put the character string in the file followed by a newline and when a null is visited put a dot, ".", followed by a newline. For example, the tree

                              
                                 a
                               /   \
                              b     c
                             /    /   \
                            d    e     f
   

   is stored as the file "a b d . . . c e . . f . ." where spaces indicate newlines.
   • Design an algorithm which outputs the preorder file format of a binary tree given a pointer to the root of a binary tree. Assume the binary tree has nodes with fields "data", "left_child", and "right_child".
   • Design an algorithm which takes a preorder file format of a binary tree and produces the binary tree. Hint: an effective approach is to design a recursive function that processes a sequence of lines in a file and returns a binary tree.
   • Is there a similar file format based on postorder traversal? If not why not? If so, then explain how to modify the algorithm for producing the tree from the preorder file format to an algorithm for producing the tree from the postorder file format.
2. (10 points) Using an in-order traversal it is quite easy to output all the data in a binary search tree in order. Design an algorithm which when given a binary search tree and two numbers x and y outputs all the data items z in order with the property that x <= z <= y. If the tree has height d then the total time to output should be O(d + k) where k is the number of data items output by the call. You should argue that your algorithm takes that much time.