6.s096 2013

Assignment 4

Assignments are due at midnight after the following lecture. This assignment is due on Thursday, January 24 at 11:59pm (deadline extended from Tuesday, January 22).

The companion lecture was Lecture 4: Data Structures and Debugging.

- Problem

Today's assignment combines the material from the past few lectures. Your job is to fill in the skeleton code we provide. I have commented the code with what each section should do.

Tarball of Code
Zip of Code

Your job is to implement a binary search tree, a data structure of connected nodes with a tree shape. Each node has a node identifier (a number), data (payload), and 2 children (left and right). The children are other nodes referenced with a pointer, with the constraint that the left node's id is less than the parent node's id, and the right node's id is larger than the parent node id. No two nodes will have the same identifier. A node can have less than two children; in that case, one or more of its child pointers can be NULL.

user.c contains the main() function. We will replace this function with one for grading. You should use your main() function to test that your functions to insert into and search the binary tree work correctly.

Your job is to complete the data structure and function declarations in bintree.h, then complete the implementation of your functions in bintree.c. If you want to define additional functions to simplify your program, that's fine. You cannot change the return types or argument types of the included functions, though. Even though we don't require the deletion function, make sure to free all memory you allocate!

Make sure your program compiles without warning, runs, and definitely use valgrind to ensure you have no memory leaks. If we find any…uh oh :O

$ gcc -Wall -std=c99 user.c bintree.c -o bintree
$ ./bintree
<your test output>

- Submit

Do not submit using both methods if you can avoid it. We'll make our best effort to use the submission that looks more recent, but make no guarantees.

Athena Submission

If you're working on Athena, this is the easier way to submit. It's still being tested, though, so if you have any problems, tell us about them and submit with Stellar instead.

Just change into your assignment directory and invoke our athrun 6.s096 submit-assignment command like this:

$ cd assignment4
$ ls
$ athrun 6.s096 submit-assignment . assignment4
├── bintree.c
├── bintree.h
└── user.c

0 directories, 3 files
$ echo heck yeah
heck yeah

Stellar Submission

Submit your version of the source files on Stellar.

That's easiest from an Athena cluster, but you can download your files from Athena too. First, compress them with a command like this:

tar zcvf assignment4-athenaid.tar.gz *.c *.h

Then you can download them with SCP. WinSCP is a good client for Windows. On Linux and OS X, you can use the scp command:

scp athenaid@athena.dialup.mit.edu:assignment4/assignment4-athenaid.tar.gz .

(Note the period at the end of the scp command!)