Contents

Overview

We saw in class and on the Binary Search Tree topic how to insert data into a tree. In this assignment, you will be implementing that method.

(Back to top)

Requirements

I'm providing you with a templated BST with limited functionality—there're no contains(item), remove(item), isEmpty(), or size() methods. There are, however, stubs for the insert(item) and insertHelper(item, node) methods—these are what you have to implement. Luckily, the pseudo code is already provided for you over one the BST topic page, so this shouldn't be a herculean task. The code I'm providing you with contains a main that builds a BST. Once you have finished implementing the insert methods, you can test it by compiling and running the program. You should see the following output:

$ ./bst
2, 5, 6, 10, 17, 25, 

Here is the code for this homework. Unlike previous homeworks, I've stuck the class in the same file as main. This is generally bad form, but I'm feeling lazy. Look for the // TODO:... comments for the stubs you have to implement.

(Back to top)

Checklist

• the code compiles (2 points)
• the program runs correctly (2 points)
• insert(item) is fully implemented (1 point)
• insertHelper(item, node) is fully implemented (2 points)
• the code is well documented (1 point)
• the file has the header (see the style guidelines), including who you've collaborated with (1 point)
• all code follows the style guidelines (1 point)

(Back to top)

Extra credit

Extra credit will be capped at 5 points.

EC-1 (2 points)

Turn your assignment in a day early—by Sunday night at 11:59pm.

EC-2 (1 point)

Implement the size() and isEmpty() methods.

EC-3 (2 points)

Implement the contains(item) method.

EC-4 (3 points)

Implement the remove(item) method.

(Back to top)

Submissions

Everything should be uploaded to Canvas by the deadline posted.

(Back to top)