BST FAQ

In a Binary Search Tree, you have a lot of nodes with pointers to other nodes. Whenever it comes time to add or remove nodes, you have to change what these pointers point to. However, if you simply pass a pointer into an add or remove function, you will pass a copy of the pointer instead of the original one. Then, when you try to change what the pointer points to, you will end up only changing the copy, while the original pointer (and therefore, the entire tree) remains unchanged. Passing a pointer by reference allows you to change the original pointer instead of making a copy.

Writing a function that accepts a reference to a pointer is simple. All you need to do is add an ampersand character (&) immediately following the asterisk (*). If I have the following function:

bool insert(Node* node);

Changing it to accept a reference to a pointer is as simple as adding an ampersand:

bool insert(Node*& node);

Passing to a function that accepts a reference to a pointer has the exact same syntax as passing to a function that takes a pointer.

Removing a node with a single child is a simple process. You simply replace it with its child. However, removing a node with two children is slightly more involved.

Removing a node with two children can be done in several ways, but for the sake of consistency, we will all do it the same way for this class.

The first thing to do is to find the "inorder predecessor." In other words, this means finding the largest node on the left side of the tree. To do this, go to the left child of the node you are trying to delete, and then recursively go to each right child until there are no more right children. The last right child is the inorder predecessor.

Once this is done, you will replace the node you are trying to delete with the inorder predecessor. If the inorder predecessor had a left child before you moved it, the left child will take its original place.

There is a link to a BST simulator on the main lab page that will allow you to see this process visually.

A level-order tree traversal visits each level of the tree and prints every value on the current level before moving to the next level. The root node is on level 0, its children are on level 1, and so forth.

Memory leaks often frustrate students, but they're actually easy to find if you use this simple procedure. Many leak checkers are comparable to putting a paper towel under a leaking fish tank; they don't really tell you where the leak occurred (or if they try to it's not very helpful) but that there is one. Try following this procedure to find where the memory leak is occurring:

1. Look at the test case you're running. Shave off a couple of lines and run the program. Did the memory leak go away?
2. Keep removing lines from your test file until the memory leak goes away. Whichever was the last one removed is the case that was causing the leak.
3. Form a hypothesis about why that case was causing a leak. For example, if the case that causes the leak for you is when you insertTail on an empty list, your hypotheses may be that you missed checking for that condition in your insertTail function.
4. Create your own test case for that hypothesis. Try to recreate the error in as few lines as possible. This is important because it allows you simplify the case down so it's easier to comprehend as you walk through your code. If you can't recreate the memory leak maybe try a different hypothesis.
5. Walk that test case through your code. In an IDE you can use breakpoints, otherwise you can always use cout statements. You should have a good idea of what each variable's value should be at each step. It may be helpful (as in definitely helpful) to draw a picture of what's going on.

• Do you have a destructor? Remember that you don't call clear on a vector when you're done with it. It does that for you in the destructor.
• Do you initialize all of your data members? Use your constructor!!
• Do you delete everything that you allocate? Look at the types that you allocate. Are you sure that you have a delete for every object that you allocate?