CS 261 Assignment 3 with Extra Credit

.gitignore

*.o
test_bst
test_bst_iterator
*.dSYM

README.md

Assignment 3

Due at 11:59pm on Monday, 11/18/2019

Demo due by 11:59pm on Friday 12/6/2019

This assignment is intended to have you start to explore non-linear data structures by implementing a binary search tree (BST). The requirements for the assignment are described below.

For this assignment, you are provided with some starter code that defines the structures you'll be working with and prototypes the functions you'll be writing and also provides some data structures upon which to build a BST implementation. It's important that you don't modify the function prototypes specified in bst.h. To help grade your assignment, we will use a set of tests that assume these functions exist and have the same prototypes that are defined in those files. If you change the prototypes, it will cause the tests to break, and your grade for the assignment will likely suffer.

Feel free to add any additional functions you might need to bst.c.

Implement a binary search tree

Your main task for this assignment is to implement a binary search tree (BST). A BST is a tree-structured data type that allows fast insertions, lookups, and removals by structuring itself in a way that encodes the behavior of binary search. Specifically, each node in a BST has at most two children, a left child and a right child, and every node satisfies the BST property, which requires that all values stored in a node's left subtree must be less than that node's value, while all values stored in a node's right subtree must be greater than or equal to that node's value.

For this assignment, the interface for the BST you'll implement (i.e. the structures and the prototypes of functions a user of the BST interacts with) is already defined for you in the file bst.h. Your first task in this assignment is to implement definitions for the functions that comprise this interface in bst.c.

Note that you may not modify the interface definition with which you are provided. Specifically, do not modify any of the already-defined BST function prototypes. We will use a set of tests to verify your implementation, and if you change the BST interface, it will break these tests, thereby (negatively) affecting your grade. You may also not modify any of the existing structures defined in the starter code (i.e. struct bst and struct bst_node). Beyond these things, though, feel free to add any additional functions or structures your BST implementation needs.

The BST functions you'll need to implement are outlined briefly below. All of these functions use a type called struct bst, which is defined in bst.c and represents the BST itself. For more details, including information on function parameters and expected return values, see the documentation provided in bst.c.

• bst_create() - This function should allocate, initialize, and return a pointer to a new BST structure.

• bst_free() - This function should free the memory held within a BST structure created by bst_create(). Note that this function only needs to free the memory held by the BST itself. It does not need to free the individual elements stored in the BST. This is the responsibility of the calling function.

• bst_size() - This function should return the total number of elements stored in a given BST. Importantly, because you can't modify the fields of struct bst or struct bst_node, you'll have to calculate a BST's size each time this function is called. It could be helpful to think recursively here. Feel free to write any helper functions you need to make this work.

• bst_insert() - This function should insert a new key/value pair into a given BST. The BST should be ordered based on the specified key value. In other words, your BST must always maintain the BST property among all keys stored in the tree.

• bst_remove() - This function should remove the value with a specified key from a given BST. If multiple values are stored in the tree with the same key, the first one encountered (i.e. the one closest to the root of the tree) should be removed.

• bst_get() - This function should return the value associated with a specified key in a given BST. If multiple values are stored in the tree with the same key, the first one encountered (i.e. the one closest to the root of the tree) should be returned.

Extra credit: implement an in-order BST iterator

For up to 10 points of extra credit, you can implement an iterator for your BST that returns keys/values from the BST in the same order they would be visited during an in-order traversal of the tree. In particular, for a BST, this means the iterator should return keys in ascending sorted order.

The type you'll use to implement the iterator, struct bst_iterator, is declared in bst.h and defined in bst.c. You may not change the definition of this structure by adding or modifying its fields. The one field it contains represents a stack, which means that you'll have to use a stack to help you order and store the BST's nodes during the in-order iteration (the stack implementation is provided in stack.{h,c} and list.{h,c}).

You'll also have to implement the following functions, which are defined in bst.c (with further documentation in that file):

• bst_iterator_create() - This function should allocate, initialize, and return a pointer to a new BST iterator. The function will be passed a specific BST over which to perform the iteration.

• bst_iterator_free() - This function should free the memory associated with a BST iterator created by bst_create(). It should not free any memory associated with the BST itself. That is the responsibility of the caller.

• bst_iterator_has_next() - This function should return a 0/1 value that indicates whether or not the iterator has nodes left to visit.

• bst_iterator_next() - This function should return both the key and value associated with the current node pointed to by the iterator and then advance the iterator to point to the next node in an in-order traversal. Note that the value associated with the current node must be returned via an argument to this function. See the documentation in bst.c for more about this.

To be able to earn this extra credit, your BST insertion function must be working correctly. Importantly, to earn the full 10 points of extra credit, your iterator must have worst-case space complexity of O(h), where h is the height of the BST. In other words, to earn full credit, you can't just implement a normal in-order traversal of the BST that stores all of the tree's nodes in the correct order in the iterator's stack. You'll have to be more clever.

Hint: To implement this iterator so that it has O(h) space complexity, try to mimic the way a recursive in-order traversal works. In particular, think about the way that each node in a BST "waits" to be visited/processed while its entire left subtree is explored. Then after that node is visited/processed, its entire right subtree is explored. Can you use the stack with which you're provided to implement this "waiting" behavior? In particular, can you put BST nodes onto the stack in such a way that the top of the stack always represents the next node to be visited/processed in an in-order traversal? To see how this might work, think about the way function calls are added and removed to/from the call stack during a recursive in-order BST traversal.

To test your iterator implementation, a testing application test_bst_iterator.c is provided. This application will be compiled automatically when you run make, and you can run it like so: ./test_bst_iterator. The expected output for this application is provided in the example_output/ directory.

Storing key/value pairs

It is important to note that each data element stored in your BST will actually consist of two parts: a key and a value. Under this scheme, the key will serve as a unique identifier for the data element, while the value will represent the rest of the data associated with that element. For example, if you were storing information about OSU students in your BST, the key for each student element might be that student's OSU ID number, while the corresponding value might be a struct containing all other data related to that student (e.g. name, email address, GPA, etc.). Storing data as key/value pairs is a common approach that we'll see in other data structures we explore in this course.

For your BST implementation, each data element's key will be represented as an integer value, while the associated value will be a void pointer. This is reflected in the structure you must use to represent a single node in your BST:

struct bst_node {
  int key;
  void* value;
  struct bst_node* left;
  struct bst_node* right;
};

Your BST should be organized based on the keys of the elements. In other words, the BST property must always hold among all keys in the tree. For example, when a new data element is inserted into your BST, decisions about whether to insert that element within a node's left subtree or its right subtree should be based on comparisons between the key of the element being inserted and the keys stored in the tree. Similarly, when a user wants to lookup or remove data elements stored in your BST, they will do so by specifying the key to be found/removed.

Testing your work

In addition to the skeleton code provided here, you are also provided with some application code in test_bst.c to help verify that your BST implementation, is behaving the way you want it to. In particular, the testing code calls the functions from bst.c, passing them appropriate arguments, and then prints the results. You can use the provided Makefile to compile all of the code in the project together, and then you can run the testing code as follows:

make
./test_bst

Example output of the testing program using a correct BST implementation is provided in the example_output/ directory.

In order to verify that your memory freeing functions work correctly, it will be helpful to run the testing application through valgrind.

Submission

As always, we'll be using GitHub Classroom for this assignment, and you will submit your assignment via GitHub. Just make sure your completed files are committed and pushed by the assignment's deadline to the master branch of the GitHub repo that was created for you by GitHub Classroom for this assignment. A good way to check whether your files are safely submitted is to look at the master branch of your assignment repo on the github.com website (i.e. https://github.com/osu-cs261-f19/assignment-3-YourGitHubUsername/). If your changes show up there, you can consider your files submitted.

Grading criteria

Your program MUST compile and run on flip.engr.oregonstate.edu, so make sure you have tested your work there before you make your final submission, since a program that compiles and runs in one environment may not compile and run in another. Assignments that do not compile on flip will receive a grade of 0. If you do not have an ENGR account, you can create one at https://teach.engr.oregonstate.edu/.

The assignment is worth 100 total points, broken down as follows:

• 10 points: bst_create() correctly allocates and initializes a BST
• 10 points: bst_free() correctly frees the memory allocated to a BST with no memory leaks
• 15 points: bst_size() correctly determines the number of elements in a BST
• 25 points: bst_insert() correctly inserts a key/value pair into a BST, maintaining the BST property with respect to all keys in the tree
• 25 points: bst_remove() correctly removes a key/value pair from a BST based on a specified key, maintaining the BST property with respect to all keys in the tree
• 15 points: bst_get() correctly retrieves the value associated with a given key in a BST

You can also earn up to 10 points of extra credit for implementing an in-order BST iterator as described above. Again, to earn full credit, your iterator must have worst-case O(h) space complexity, where h is the height of the tree.

bst.c

/*
 * This file is where you should implement your binary search tree.  It already
 * contains skeletons of the functions you need to implement (along with
 * documentation for each function).  Feel free to implement any additional
 * functions you might need.  Also, don't forget to include your name and
 * @oregonstate.edu email address below.
 *
 * Name:
 * Email:
 */

#include <stdlib.h>

#include "bst.h"
#include "stack.h"

/*
 * This structure represents a single node in a BST.  In addition to containing
 * pointers to its two child nodes (i.e. `left` and `right`), it contains two
 * fields representing the data stored at this node.  The `key` field is an
 * integer value that should be used as an identifier for the data in this
 * node.  Nodes in the BST should be ordered based on this `key` field.  The
 * `value` field stores data associated with the key.
 *
 * You should not modify this structure.
 */
struct bst_node {
  int key;
  void* value;
  struct bst_node* left;
  struct bst_node* right;
};


/*
 * This structure represents an entire BST.  It specifically contains a
 * reference to the root node of the tree.
 *
 * You should not modify this structure.
 */
struct bst {
  struct bst_node* root;
};

/*
 * This function should allocate and initialize a new, empty, BST and return
 * a pointer to it.
 */
struct bst* bst_create() {
  return NULL;
}

/*
 * This function should free the memory associated with a BST.  While this
 * function should up all memory used in the BST itself, it should not free
 * any memory allocated to the pointer values stored in the BST.  This is the
 * responsibility of the caller.
 *
 * Params:
 *   bst - the BST to be destroyed.  May not be NULL.
 */
void bst_free(struct bst* bst) {
  return;
}

/*
 * This function should return the total number of elements stored in a given
 * BST.
 *
 * Params:
 *   bst - the BST whose elements are to be counted.  May not be NULL.
 */
int bst_size(struct bst* bst) {
  return 0;
}

/*
 * This function should insert a new key/value pair into the BST.  The key
 * should be used to order the key/value pair with respect to the other data
 * stored in the BST.  The value should be stored along with the key, once the
 * right location in the tree is found.
 *
 * Params:
 *   bst - the BST into which a new key/value pair is to be inserted.  May not
 *     be NULL.
 *   key - an integer value that should be used to order the key/value pair
 *     being inserted with respect to the other data in the BST.
 *   value - the value being inserted into the BST.  This should be stored in
 *     the BST alongside the key.  Note that this parameter has type void*,
 *     which means that a pointer of any type can be passed.
 */
void bst_insert(struct bst* bst, int key, void* value) {
  return;
}

/*
 * This function should remove a key/value pair with a specified key from a
 * given BST.  If multiple values with the same key exist in the tree, this
 * function should remove the first one it encounters (i.e. the one closest to
 * the root of the tree).
 *
 * Params:
 *   bst - the BST from which a key/value pair is to be removed.  May not
 *     be NULL.
 *   key - the key of the key/value pair to be removed from the BST.
 */
void bst_remove(struct bst* bst, int key) {
  return;
}

/*
 * This function should return the value associated with a specified key in a
 * given BST.  If multiple values with the same key exist in the tree, this
 * function should return the first one it encounters (i.e. the one closest to
 * the root of the tree).  If the BST does not contain the specified key, this
 * function should return NULL.
 *
 * Params:
 *   bst - the BST from which a key/value pair is to be removed.  May not
 *     be NULL.
 *   key - the key of the key/value pair whose value is to be returned.
 *
 * Return:
 *   Should return the value associated with the key `key` in `bst` or NULL,
 *   if the key `key` was not found in `bst`.
 */
void* bst_get(struct bst* bst, int key) {
  return NULL;
}

/*****************************************************************************
 **
 ** BST iterator definition (extra credit only)
 **
 *****************************************************************************/

/*
 * Structure used to represent a binary search tree iterator.  It contains
 * only a reference to a stack to be used to implement the iterator.
 *
 * You should not modify this structure.
 */
struct bst_iterator {
  struct stack* stack;
};

/*
 * This function should allocate and initialize an iterator over a specified
 * BST and return a pointer to that iterator.
 *
 * Params:
 *   bst - the BST for over which to create an iterator.  May not be NULL.
 */
struct bst_iterator* bst_iterator_create(struct bst* bst) {
  return NULL;
}

/*
 * This function should free all memory allocated to a given BST iterator.
 * It should NOT free any memory associated with the BST itself.  This is the
 * responsibility of the caller.
 *
 * Params:
 *   iter - the BST iterator to be destroyed.  May not be NULL.
 */
void bst_iterator_free(struct bst_iterator* iter) {
  return;
}

/*
 * This function should indicate whether a given BST iterator has more nodes
 * to visit.  It should specifically return 1 (true) if the iterator has at
 * least one more node to visit or 0 (false) if it does not have any more
 * nodes to visit.
 *
 * Param:
 *   iter - the BST iterator to be checked for remaining nodes to visit.  May
 *     not be NULL.
 */
int bst_iterator_has_next(struct bst_iterator* iter) {
  return 0;
}

/*
 * This function should return both the value and key associated with the
 * current node pointed to by the specified BST iterator and advnce the
 * iterator to point to the next node in the BST (in in-order order).
 *
 * Because a function can't return two things, the key associated with the
 * current node should be returned the normal way, while its value should be
 * returned via the argument `value`.  Specifically, the argument `value`
 * is a pointer to a void pointer.  The current BST node's value (a void
 * pointer) should be stored at the address represented by `value` (i.e. by
 * dereferencing `value`).  This will look something like this:
 *
 *   *value = current_node->value;
 *
 * Parameters:
 *   iter - BST iterator.  The key and value associated with this iterator's
 *     current node should be returned, and the iterator should be updated to
 *     point to the next node in the BST (in in-order order).  May not be NULL.
 *   value - pointer at which the current BST node's value should be stored
 *     before this function returns.
 *
 * Return:
 *   This function should return the key associated with the current BST node
 *   pointed to by `iter`.
 */
int bst_iterator_next(struct bst_iterator* iter, void** value) {
  if (value) {
    *value = NULL;
  }
  return 0;
}

bst.h

/*
 * This file contains the definition of the interface for the binary search
 * tree you'll implement.  You should not modify anything in this file.  You
 * can find descriptions of the binary search tree functions, including their
 * parameters and their return values, in bst.c.
 */

#ifndef __BST_H
#define __BST_H

/*
 * Structure used to represent a binary search tree.
 */
struct bst;

/*
 * Binary search tree interface function prototypes.  Refer to bst.c for
 * documentation about each of these functions.
 */
struct bst* bst_create();
void bst_free(struct bst* bst);
int bst_size(struct bst* bst);
void bst_insert(struct bst* bst, int key, void* value);
void bst_remove(struct bst* bst, int key);
void* bst_get(struct bst* bst, int key);

/*
 * Structure used to represent a binary search tree iterator.
 */
struct bst_iterator;

/*
 * Binary search tree iterator interface prototypes.  Refer to bst.c for
 * documentation about each of these functions.
 */
struct bst_iterator* bst_iterator_create(struct bst* bst);
void bst_iterator_free(struct bst_iterator* iter);
int bst_iterator_has_next(struct bst_iterator* iter);
int bst_iterator_next(struct bst_iterator* iter, void** value);

#endif

expected_output-test_bst_iterator.txt

$ ./test_bst_iterator
== Creating BST...

== Inserting 13 values into BST...

== Creating iterator over BST...

== Using iterator to enumerate BST: key / value (expected)
  -   8 /   8 (  8)
  -  16 /  16 ( 16)
  -  24 /  24 ( 24)
  -  32 /  32 ( 32)
  -  48 /  48 ( 48)
  -  56 /  56 ( 56)
  -  64 /  64 ( 64)
  -  80 /  80 ( 80)
  -  88 /  88 ( 88)
  -  96 /  96 ( 96)
  - 104 / 104 (104)
  - 112 / 112 (112)
  - 120 / 120 (120)

== Making sure all nodes were visited (expect 1): 1
== Making sure no nodes left to visit in iterator (expect 0): 0

list.c

/*
 * This file contains a simple implementation of a singly-linked list.  See
 * the documentation below for more information on the individual functions in
 * this implementation.  You should not modify anything in this file.
 */

#include <stdlib.h>
#include <assert.h>

#include "list.h"

/*
 * This structure is used to represent a single link in a singly-linked list.
 * It is not defined in list.h, so it is not visible to the user.
 */
struct link {
  void* val;
  struct link* next;
};

/*
 * This structure is used to represent an entire singly-linked list.  Note that
 * we're keeping track of just the head of the list here, for simplicity.
 */
struct list {
  struct link* head;
};

/*
 * This function allocates and initializes a new, empty linked list and
 * returns a pointer to it.
 */
struct list* list_create() {
  struct list* list = malloc(sizeof(struct list));
  list->head = NULL;
  return list;
}

/*
 * This function frees the memory associated with a linked list.  Freeing any
 * memory associated with values still stored in the list is the responsibility
 * of the caller.
 *
 * Params:
 *   list - the linked list to be destroyed.  May not be NULL.
 */
void list_free(struct list* list) {
  assert(list);

  /*
   * Free all individual links.
   */
  struct link* next, * curr = list->head;
  while (curr != NULL) {
    next = curr->next;
    free(curr);
    curr = next;
  }

  free(list);
}

/*
 * This function inserts a new value into a given linked list.  The new element
 * is always inserted as the head of the list.
 *
 * Params:
 *   list - the linked list into which to insert an element.  May not be NULL.
 *   val - the value to be inserted.  Note that this parameter has type void*,
 *     which means that a pointer of any type can be passed.
 */
void list_insert(struct list* list, void* val) {
  assert(list);

  /*
   * Create new link and insert at head.
   */
  struct link* link = malloc(sizeof(struct link));
  link->val = val;
  link->next = list->head;
  list->head = link;
}

/*
 * This function returns 1 if the list is empty and 0 otherwise.
 */
int list_isempty(struct list* list) {
  assert(list);
  if (list->head) {
    return 0;
  } else {
    return 1;
  }
}

/*
 * This function returns the value stored at the head of a given linked list
 * or NULL if the list is empty.
 */
void* list_head(struct list* list) {
  assert(list);

  if (list->head) {
    return list->head->val;
  } else {
    return NULL;
  }
}

/*
 * This function removes the value stored at the head of a given linked list.
 * If the list is empty, this function is a noop.
 */
void list_remove_head(struct list* list) {
  assert(list);

  if (list->head) {
    struct link* old_head = list->head;
    list->head = old_head->next;
    free(old_head);
  }
}

list.h

/*
 * This file contains the definition of the interface for a linked list.  You
 * can find descriptions of the linked list functions, including their
 * parameters and their return values, in list.c.  You should not modify
 * anything in this file.
 */

#ifndef __LIST_H
#define __LIST_H

/*
 * Structure used to represent a singly-linked list.
 */
struct list;

/*
 * Linked list interface function prototypes.  Refer to list.c for
 * documentation about each of these functions.
 */
struct list* list_create();
void list_free(struct list* list);
void list_insert(struct list* list, void* val);
int list_isempty(struct list* list);
void* list_head(struct list* list);
void list_remove_head(struct list* list);

#endif

Makefile

CC=gcc --std=c99 -g

all: test_bst test_bst_iterator

test_bst: test_bst.c bst.o stack.o list.o
	$(CC) test_bst.c bst.o stack.o list.o -o test_bst

test_bst_iterator: test_bst_iterator.c bst.o stack.o list.o
	$(CC) test_bst_iterator.c bst.o stack.o list.o -o test_bst_iterator

bst.o: bst.c bst.h
	$(CC) -c bst.c

stack.o: stack.c stack.h
	$(CC) -c stack.c

list.o: list.c list.h
	$(CC) -c list.c

clean:
	rm -f *.o test_bst

stack.c

/*
 * This file contains a simple implementation of a linked list-based stack.
 * See the documentation below for more information on the individual functions
 * in this implementation.  You should not modify anything in this file.
 */

#include <stdlib.h>
#include <assert.h>

#include "stack.h"
#include "list.h"

/*
 * This is the structure that represents a stack.  It contains a single field
 * representing a linked list that is used as the underlying data storage for
 * the stack.
 */
struct stack {
  struct list* list;
};

/*
 * This function allocates and initializes a new, empty stack and returns a
 * pointer to it.
 */
struct stack* stack_create() {
  struct stack* stack = malloc(sizeof(struct stack));
  stack->list = list_create();
  return stack;
}

/*
 * This function frees the memory associated with a stack.  Note that it does
 * not free any memory allocated to the pointer values stored in the stack.
 * This is the responsibility of the caller.
 *
 * Params:
 *   stack - the stack to be destroyed.  May not be NULL.
 */
void stack_free(struct stack* stack) {
  assert(stack);
  list_free(stack->list);
  free(stack);
}

/*
 * This function indicates whether a given stack is currently empty.  It
 * returns 1 if the specified stack is empty (i.e. contains no elements) and
 * 0 otherwise.
 *
 * Params:
 *   stack - the stack whose emptiness is being questioned.  May not be NULL.
 */
int stack_isempty(struct stack* stack) {
  assert(stack);
  return list_isempty(stack->list);
}

/*
 * This function pushes a new value onto a given stack.  The value to be
 * pushed is specified as a void pointer.
 *
 * Params:
 *   stack - the stack onto which a value is to be pushed.  May not be NULL.
 *   val - the value to be pushed.  Note that this parameter has type void*,
 *     which means that a pointer of any type can be passed.
 */
void stack_push(struct stack* stack, void* val) {
  assert(stack);
  list_insert(stack->list, val);
}

/*
 * This function returns the value stored at the top of a given stack *without*
 * removing that value.
 *
 * Params:
 *   stack - the stack from which to query the top value.  May not be NULL.
 */
void* stack_top(struct stack* stack) {
  assert(stack);
  return list_head(stack->list);
}

/*
 * This function pops a value from a given stack and return the popped value.
 *
 * Params:
 *   stack - the stack from which a value is to be popped.  May not be NULL.
 *
 * Return:
 *   This function returns the value that was popped.
 */
void* stack_pop(struct stack* stack) {
  assert(stack);
  void* head = list_head(stack->list);
  list_remove_head(stack->list);
  return head;
}

stack.h

/*
 * This file contains the definition of the interface for the stack you'll
 * implement.  You can find descriptions of the stack functions, including
 * their parameters and their return values, in stack.c.  You should not
 * modify anything in this file.
 */

#ifndef __STACK_H
#define __STACK_H

/*
 * Structure used to represent a stack.
 */
struct stack;

/*
 * Stack interface function prototypes.  Refer to stack.c for documentation
 * about each of these functions.
 */
struct stack* stack_create();
void stack_free(struct stack* stack);
int stack_isempty(struct stack* stack);
void stack_push(struct stack* stack, void* val);
void* stack_top(struct stack* stack);
void* stack_pop(struct stack* stack);

#endif

test_bst_iterator.c

/*
 * This file contains executable code for testing your BST iterator
 * implementation.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "bst.h"

/*
 * This is the data that's used to test this program.  It forms a tree that
 * looks like this:
 *
 *               64
 *              /  \
 *             /    \
 *            /      \
 *           /        \
 *          32        96
 *         /  \      /  \
 *        /    \    /    \
 *       16    48  80    112
 *      /  \     \   \   /  \
 *     8   24    56  88 104 120
 */
#define NUM_TEST_DATA 13
const int TEST_DATA[NUM_TEST_DATA] =
  {64, 32, 96, 16, 48, 80, 112, 8, 24, 56, 88, 104, 120};

/*
 * This is a helper function that's used to compare integers when sorting with
 * qsort().
 */
int cmp_ints(const void* a, const void* b) {
  return *(int*)a - *(int*)b;
}

int main(int argc, char** argv) {
  /*
   * Create a new BST and insert the testing data into it.  The testing data
   * is inserted in such a way that the value is equal to the address of the
   * corresponding key (which comes from the TEST_DATA array above).  In other
   * words, for any given key, we'll be able to verify that the tree contains
   * the correct value by comparing key == *value.
   */
  printf("== Creating BST...\n");
  struct bst* bst = bst_create();
  printf("\n== Inserting %d values into BST...\n", NUM_TEST_DATA);
  for (int i = 0; i < NUM_TEST_DATA; i++) {
    bst_insert(bst, TEST_DATA[i], (void*)&TEST_DATA[i]);
  }

  /*
   * Create a sorted copy of the test data to simulate the order in which
   * keys should be visited in an in-order traversal of the BST.
   */
  int* sorted = malloc(NUM_TEST_DATA * sizeof(int));
  memcpy(sorted, TEST_DATA, NUM_TEST_DATA * sizeof(int));
  qsort(sorted, NUM_TEST_DATA, sizeof(int), cmp_ints);

  /*
   * Create an iterator and use it to enumerate the values in the BST in order.
   * Use the array of sorted keys created above to make sure that the keys and
   * values are returned by the iterator in the correct order.
   */
  printf("\n== Creating iterator over BST...\n");
  struct bst_iterator* iter = bst_iterator_create(bst);
  int* value;
  int key, k = 0;
  printf("\n== Using iterator to enumerate BST: key / value (expected)\n");
  while (k < NUM_TEST_DATA && bst_iterator_has_next(iter)) {
    key = bst_iterator_next(iter, (void**)&value);
    if (value) {
      printf("  - %3d / %3d (%3d)\n", key, *value, sorted[k]);
    } else {
      printf("  - value unexpectedly NULL for key %3d (expected %3d)\n", key,
        sorted[k]);
    }
    k++;
  }

  printf("\n== Making sure all nodes were visited (expect 1): %d\n",
    k == NUM_TEST_DATA);
  printf("== Making sure no nodes left to visit in iterator (expect 0): %d\n",
    bst_iterator_has_next(iter));

  free(sorted);
  bst_iterator_free(iter);
  bst_free(bst);

  return 0;
}