Practice Exercise

Your task is to write a function, treeCopy, that copies a tree up to a given depth. If the given depth is negative, you should return an empty tree. If the given depth is greater than the height of the tree, you should return a copy of the entire tree.

Download

While in your practice exercises directory, run the following command:

unzip /web/cs2521/practice-exercises/trees/treeCopy/downloads/treeCopy.zip

If you're working at home, download treeCopy.zip by clicking on the above link and then unzip the downloaded file.

Files

tree.c	Contains code for reading and printing a binary tree
tree.h	Contains the definition of the binary tree data structure and function prototypes
testTreeCopy.c	Contains the main function, which reads in a binary tree from standard input, calls treeCopy, and prints out the result.
treeCopy.c	Contains treeCopy, the function you must implement
Makefile	A makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic tests
autotest	A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually.

Examples

./testTreeCopy
Enter the preorder traversal of the tree: 4 2 1 3 6 5 7
Enter the in-order traversal of the tree: 1 2 3 4 5 6 7
Enter depth: 1

Tree:

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

Copy of the tree up to depth 1:

  4
 / \
2   6

./testTreeCopy
Enter the preorder traversal of the tree: 2 1 4 3 6 5
Enter the in-order traversal of the tree: 1 2 3 4 5 6
Enter depth: 0

Tree:

  2
 / \
1   4
   / \
  3   6
     /
    5

Copy of the tree up to depth 0:

2

./testTreeCopy
Enter the preorder traversal of the tree: 4 1 7
Enter the in-order traversal of the tree: 1 4 7
Enter depth: -1

Tree:

  4
 / \
1   7

Copy of the tree up to depth -1:

X

Testing

You can compile and test your function using the following commands:

make                            # compiles the program
./testTreeCopy                  # tests with manual input, outputs to terminal
./testTreeCopy < input-file     # tests with input from a file, outputs to terminal
./testTreeCopy < tests/01.in    # for example, tests with input from tests/01.in
                                  # (then manually compare with tests/01.exp)

After you have manually tested your solution, you can autotest it by running ./autotest. This will run some basic tests on your program, as well as check for memory leaks/errors.

It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.