Setup
Follow this link to a zip file containing a Makefile, the C unit test framework header file tests.h, a set of unit tests in bst_test.c, and the binary tree module files, bst.h and bst.c.
Problem
For this exercise you’ll debug a binary search tree module, where the values in the tree are C strings. The interface to the module is in bst.h, and the (buggy) implementation is in bst.c. You should read both of these files to be sure you understand what data structures and functions are integral to the module.
Run make, which will compile the source, create the executable bst_test.exe, and run the tests. Note that the make file builds a debug version (-g) of the program. Based on the output from the tests, edit the implementation file bst.c, locate the error(s), and repair them. Update the header comment of bst.c with notes indicating the error(s) you found and what you did to repair them. Remake the executable and run the tests again. Do this until all tests pass. As always you are encouraged to draw a picture of the binary tree with the test data to aid in your debugging effort.
For the record, there are at most three seeded errors in the module.
A successful run of the given test cases looks like this (although you may want to start with your own test cases…)
./bst_test
> Nothing
in the list initially...
> Put mike
in the list...
> Put zeke
in the list...
> Put andy
in the list...
> Put bart
in the list...
> Put tom
in the list...
--- Results
---
Tests
run: 6
Passes: 30
Failures: 0
Submission
Make a pushbox submission of your updated bst.c file to a directory named "BST-Debug"