CSE 326, Spring 1997: Homework 3

Due 4/23/97

When asked to design an algorithm please provide the pseudocode with enough explanation that it can be understood easily.

  1. (20 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 ".", writes a string into a file, or reads 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
                                /   \
                               b     c
                              /    /   \
                             d    e     f
    is stored as the file "a b d . . . c e . . f . ." where spaces indicate newlines.
  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.