The purpose of this lab is to introduce you to techniques for debugging programs on embedded systems. After completing this lab, you should be able to:

• Identify and fix C syntax errors
• Understand and fix common compile time errors
• Identify code that does not conform to common C formatting standards and make the appropriate changes
• Use the debugger to

Watch local and global variables

Check the contents of memory

Set breakpoints

Step through code

• Correct logic errors

About the Project

In this lab, youll be debugging a program that uses binary search trees.

The binary search tree struct stores the address of the root node and the number of nodes currently stored in the tree. This is implemented using the bst_t structure, as defined in bst.h.

Every node within the tree stores the addresses of both the left and right children (NULL if there is no child there) as well as the integer value stored in this node (of type S32). This is implemented using the bst_n structure, as defined in bst.h.

The bst.c file implements the following functions (with some errors you will need to fix) to manipulate the binary search tree with n nodes and a height h :

void bst_init( bst_t * );

Initialize the binary search tree so that it is empty. Run time: (1)

U32 bst_size();

Return the number of nodes in the binary search tree. Run time: (1)

bool bst_insert( bst_t *, S32 );

Insert the given integer into the binary search tree and return false if the node is already in the tree

(do not add a duplicate into the tree) and true otherwise. Run time: O(h)

S32 bst_min( bst_t * );

Returns the smallest integer in the binary search tree. Return

2

INT_MAX if the tree is empty. Run time: O(h)

S32 bst_max( bst_t * );

Returns the largest integer in the binary search tree. Return INT_MIN if the tree is empty. Run time: O(h)

bool bst_erase( bst_t *, S32 );

If the object is in the binary search tree, remove it and return true; otherwise, return false and do nothing. Run time: O(h)

While completing the various exercises, you are welcome to create other helper functions and you are welcome to add additional fields onto any of the records as you find necessary.

#include <stdbool.h> has been added to allow access to the type bool .

#include <limits.h> is used to access INT_MIN and INT_MAX .

Goals

Your goals in this lab are as follows:

1. Fix the syntax errors so that the code compiles with 0 errors and 0 warnings.
2. Improve the C formatting and style, and fill in the comments block at the top of bst.c to document what you changed.
3. Fix the logic errors so the program produces the output shown below. There are four logic errors, but one of them (interestingly) has no impact on the results. Remember to fill in the comment block at the top of bst.c to document what you changed.

Expected output: