Binary Search Tree Implementation

Question

I've searched the forum, and tried to implement the code in the threads I found. But I've been working on this real simple program since about 10am, and can't solve the seg. faults for the life of me.

Any ideas on what I'm doing wrong would be greatly appreciated.

BST.h (All the implementation problems should be in here, and this has been updated some to reflect further development work, look at the history to see old versions.)

#ifndef BST_H_
#define BST_H_

#include <stdexcept>
#include <iostream>
#include "btnode.h"

using namespace std;

/*
    A class to represent a templated binary search tree.
*/
template <typename T>
class BST
{
    private:

        //pointer to the root node in the tree
        BTNode<T>* root;

    public:

        //default constructor to make an empty tree
        BST();

        /*
            You have to document these 4 functions
        */
        void insert(T value);
        bool search(const T& value) const;
        bool search(BTNode<T>* node, const T& value) const;
        void printInOrder() const;
        void remove(const T& value);

        //function to print out a visual representation
        //of the tree (not just print the tree's values 
        //on a single line)
        void print() const;

    private:

        //recursive helper function for "print()"
        void print(BTNode<T>* node,int depth) const;
};

/*
    Default constructor to make an empty tree
*/
template <typename T>
BST<T>::BST()
{
    root = NULL;
}

template <typename T>
void BST<T>::insert(T value)
{
    BTNode<T>* newNode = new BTNode<T>(value);
    cout << newNode->data;
    if(root == NULL)
    {
        root = newNode;
        return;
    }
    BTNode<T>* current = root;
    while(true)
    {
        if(current->left == NULL && current->right == NULL)
            break;
        if(current->right != NULL && current->left != NULL)
        {
            if(newNode->data > current->data) 
                current = current->right;
            else if(newNode->data < current->data)
                current = current->left;
        }
        else if(current->right != NULL && current->left == NULL)
        {
            if(newNode->data < current->data) 
                break;
            else if(newNode->data > current->data)
                current = current->right;
        }
        else if(current->right == NULL && current->left != NULL)
        {
            if(newNode->data > current->data) 
                break;
            else if(newNode->data < current->data)
                current = current->left;
        }
    }

    if(current->data > newNode->data)
    {   
        current->left = newNode;
    /*  cout << current->data << "DATA" << endl;
        cout << &current << "ADDY" << endl;
        cout << &current->left << "L ADDY" << endl;
        cout << &current->right << "R ADDY" << endl;*/
    }
    else
    {
        current->right = newNode;
        /*cout << current->data << "DATA" << endl;
        cout << &current << "ADDY" << endl;
        cout << &current->left << "L ADDY" << endl;
        cout << &current->right << "R ADDY" << endl;*/
    }
    return;
}

//public helper function
template <typename T>
bool BST<T>::search(const T& value) const
{
    return(search(root,value)); //start at the root
}

//recursive function
template <typename T>
bool BST<T>::search(BTNode<T>* node, const T& value) const 
{
    if(node == NULL || node->data == value)
        return(node != NULL); //found or couldn't find value
    else if(value < node->data)
        return search(node->left,value); //search left subtree
    else
        return search(node->right,value); //search right subtree
}

template <typename T>
void BST<T>::printInOrder() const
{
    //print out the value's in the tree in order
    //
    //You may need to use this function as a helper
    //and create a second recursive function
    //(see "print()" for an example)
}

template <typename T>
void BST<T>::remove(const T& value)
{
    if(root == NULL)
    {
        cout << "Tree is empty. No removal. "<<endl;
        return;
    }
    if(!search(value))
    {
        cout << "Value is not in the tree. No removal." << endl;
        return;
    }
    BTNode<T>* current = root;
    BTNode<T>* parent;

    cout << root->data << " ROOT" << endl;
    cout << current->data << "CURRENT BEFORE" << endl;

    while(current != NULL)
    {
        if(root->data == value)
        {
            delete current;
            return;
        }
        else if(value > current->data)
        {
            parent = current; 
            current = current->right;
        }
        else
        {
            parent = current; 
            current = current->left;            
        }
    }
    cout << current->data << "CURRENT AFTER" << endl;

  // 3 cases :
    //We're looking at a leaf node

    if(current->left == NULL && current->right == NULL)             // It's a leaf
    {
        if(parent == current)
            delete parent;
        else if(parent->left == current)
        {
            parent->left = NULL;
            delete current;
        }
        else 
        {
            parent->right = NULL;
            delete current;
        }
        cout << "The value " << value << " was removed." << endl;
        return;
    }

    // Node with single child
    if((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL))
    {
        if(current->left == NULL && current->right != NULL)
        {
            if(parent->left == current)
            {
                parent->left = current->right;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
            else
            {
                parent->right = current->right;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
        }
        else // left child present, no right child
        {
            if(parent->left == current)
            {
                parent->left = current->left;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
            else
            {
                parent->right = current->left;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
        }
        return;
    }

    //Node with 2 children - Replace node with smallest value in right subtree.
    if (current->left != NULL && current->right != NULL)
    {
        BTNode<T>* check;
        check = current->right;
        if((check->left == NULL) && (check->right == NULL))
        {
            current = check;
            delete check;
            current->right = NULL;
            cout << "The value " << value << " was removed." << endl;
        }
        else // right child has children
        {
            //if the node's right child has a left child; Move all the way down left to locate smallest element
            if((current->right)->left != NULL)
            {
                BTNode<T>* leftCurrent;
                BTNode<T>* leftParent;
                leftParent = current->right;
                leftCurrent = (current->right)->left;
                while(leftCurrent->left != NULL)
                {
                    leftParent = leftCurrent;
                    leftCurrent = leftCurrent->left;
                }
                current->data = leftCurrent->data;
                delete leftCurrent;
                leftParent->left = NULL;
                cout << "The value " << value << " was removed." << endl;
            }
            else
            {
                BTNode<T>* temp;
                temp = current->right;
                current->data = temp->data;
                current->right = temp->right;
                delete temp;
                cout << "The value " << value << " was removed." << endl;
            }
        }
        return;
    }
}

/*
    Print out the values in the tree and their
    relationships visually.  Sample output:

                        22
                18
        15
10
                9
        5
                3
                        1
*/
template <typename T>
void BST<T>::print() const
{
    print(root,0);
}

template <typename T>
void BST<T>::print(BTNode<T>* node,int depth) const
{
    if(node == NULL)
    {
        std::cout << std::endl;
        return;
    }

    print(node->right,depth+1);
    for(int i=0; i < depth; i++)
    {
        std::cout << "\t";
    }
    std::cout << node->data << std::endl;
    print(node->left,depth+1);
}

#endif

main.cpp

#include "bst.h"    
#include <iostream>
using namespace std;

int main()
{
    BST<int> tree;
    cout << endl << "LAB #13 - BINARY SEARCH TREE PROGRAM" << endl;
    cout << "----------------------------------------------------------" << endl;
    // Insert.
    cout << endl << "INSERT TESTS" << endl;         // No duplicates allowed.
    tree.insert(0);
    tree.insert(5);
    tree.insert(15);
    tree.insert(25);
    tree.insert(20);

    // Search.
    cout << endl << "SEARCH TESTS" << endl;
    int x = 0;
    int y = 1;
    if(tree.search(x))
        cout << "The value " << x << " is on the tree." << endl;
    else 
        cout << "The value " << x << " is NOT on the tree." << endl;
    if(tree.search(y))
        cout << "The value " << y << " is on the tree." << endl;
    else
        cout << "The value " << y << " is NOT on the tree." << endl;

    // Removal.
    cout << endl << "REMOVAL TESTS" << endl;
    tree.remove(0);
    tree.remove(1);
    tree.remove(20);

    // Print.
    cout << endl << "PRINTED DIAGRAM OF BINARY SEARCH TREE" << endl;
    cout << "----------------------------------------------------------" << endl;
    tree.print();
    cout << endl << "Program terminated. Goodbye." << endl << endl;
}

BTNode.h

#ifndef BTNODE_H_
#define BTNODE_H_

#include <iostream>

/*
    A class to represent a node in a
    binary search tree.
*/
template <typename T>

    class BTNode
    {
        public:

            //constructor
            BTNode(T d);

            //the node's data value
            T data;

            //pointer to the node's left child
            BTNode<T>* left;

            //pointer to the node's right child
            BTNode<T>* right;
    };

    /*
        Simple constructor.  Sets the data
        value of the BTNode to "d" and defaults its
        left and right child pointers to NULL.
    */
    template <typename T>
    BTNode<T>::BTNode(T d)
    : left(NULL), right(NULL)
    {
        data = d;
    }

    #endif

Thanks.

Answer 1

Since it's homework, I'm going to help you help yourself. The first thing you should do is to code up a dump function which spits out the tree in readable form, showing, for every node:

• address of current node.
• value of current node.
• address of left node pointer.
• address of right node pointer.

Then call that dump function after every insert and delete. This is standard debugging 101 and you can, if you wish, leave that code in. It may well garner more marks from your educator if you show them you have the smarts to write unit testing code.

Answer 2

insert has a memory leak. These three lines:

BTNode<T>* current = new BTNode<T>(NULL);
current = root;
current->data = root->data;

should read:

BTNode<T>* current = root;

The whole function has somewhat contorted logic and could be smooshed down to about 1/4th its current size by thinking through the cases carefully and compressing them.

Also, here's a hint as to why you're getting a segment fault in remove. It's fairly obvious, and not because any other part of your code is broken. Debuggers are your friend.

The hint is, what does this block of code do in remove? Think carefully:

BTNode<T>* current;
BTNode<T>* parent;
current = root;
parent->left = NULL;
parent->right = NULL;

Answer 3

Here's the updated BST.h. I now have the insertion working correctly, but I'm still stuck on the remove/seg faults. I've gone through it several times and I don't see where I am leaking memory.

Any "pointers" to what's wrong would be great.

    #ifndef BST_H_
#define BST_H_

#include <stdexcept>
#include <iostream>
#include "btnode.h"

using namespace std;

/*
    A class to represent a templated binary search tree.
*/
template <typename T>
class BST
{
    private:

        //pointer to the root node in the tree
        BTNode<T>* root;

    public:

        //default constructor to make an empty tree
        BST();

        /*
            You have to document these 4 functions
        */
        void insert(T value);
        bool search(const T& value) const;
        bool search(BTNode<T>* node, const T& value) const;
        void printInOrder() const;
        void remove(const T& value);

        //function to print out a visual representation
        //of the tree (not just print the tree's values 
        //on a single line)
        void print() const;

    private:

        //recursive helper function for "print()"
        void print(BTNode<T>* node,int depth) const;
};

/*
    Default constructor to make an empty tree
*/
template <typename T>
BST<T>::BST()
{
    root = NULL;
}

template <typename T>
void BST<T>::insert(T value)
{
    BTNode<T>* newNode = new BTNode<T>(value);
    cout << newNode->data;
    if(root == NULL)
    {
        root = newNode;
        return;
    }
    BTNode<T>* current = root;
    while(true)
    {
        if(current->left == NULL && current->right == NULL)
            break;
        if(current->right != NULL && current->left != NULL)
        {
            if(newNode->data > current->data) 
                current = current->right;
            else if(newNode->data < current->data)
                current = current->left;
        }
        else if(current->right != NULL && current->left == NULL)
        {
            if(newNode->data < current->data) 
                break;
            else if(newNode->data > current->data)
                current = current->right;
        }
        else if(current->right == NULL && current->left != NULL)
        {
            if(newNode->data > current->data) 
                break;
            else if(newNode->data < current->data)
                current = current->left;
        }
    }

    if(current->data > newNode->data)
    {   
        current->left = newNode;
    /*  cout << current->data << "DATA" << endl;
        cout << &current << "ADDY" << endl;
        cout << &current->left << "L ADDY" << endl;
        cout << &current->right << "R ADDY" << endl;*/
    }
    else
    {
        current->right = newNode;
        /*cout << current->data << "DATA" << endl;
        cout << &current << "ADDY" << endl;
        cout << &current->left << "L ADDY" << endl;
        cout << &current->right << "R ADDY" << endl;*/
    }
    return;
}

//public helper function
template <typename T>
bool BST<T>::search(const T& value) const
{
    return(search(root,value)); //start at the root
}

//recursive function
template <typename T>
bool BST<T>::search(BTNode<T>* node, const T& value) const 
{
    if(node == NULL || node->data == value)
        return(node != NULL); //found or couldn't find value
    else if(value < node->data)
        return search(node->left,value); //search left subtree
    else
        return search(node->right,value); //search right subtree
}

template <typename T>
void BST<T>::printInOrder() const
{
    //print out the value's in the tree in order
    //
    //You may need to use this function as a helper
    //and create a second recursive function
    //(see "print()" for an example)
}

template <typename T>
void BST<T>::remove(const T& value)
{
    if(root == NULL)
    {
        cout << "Tree is empty. No removal. "<<endl;
        return;
    }
    if(!search(value))
    {
        cout << "Value is not in the tree. No removal." << endl;
        return;
    }
    BTNode<T>* current = root;
    BTNode<T>* parent;

    cout << root->data << " ROOT" << endl;
    cout << current->data << "CURRENT BEFORE" << endl;

    while(current != NULL)
    {
        if(root->data == value)
        {
            delete current;
            return;
        }
        else if(value > current->data)
        {
            parent = current; 
            current = current->right;
        }
        else
        {
            parent = current; 
            current = current->left;            
        }
    }
    cout << current->data << "CURRENT AFTER" << endl;

  // 3 cases :
    //We're looking at a leaf node

    if(current->left == NULL && current->right == NULL)             // It's a leaf
    {
        if(parent == current)
            delete parent;
        else if(parent->left == current)
        {
            parent->left = NULL;
            delete current;
        }
        else 
        {
            parent->right = NULL;
            delete current;
        }
        cout << "The value " << value << " was removed." << endl;
        return;
    }

    // Node with single child
    if((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL))
    {
        if(current->left == NULL && current->right != NULL)
        {
            if(parent->left == current)
            {
                parent->left = current->right;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
            else
            {
                parent->right = current->right;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
        }
        else // left child present, no right child
        {
            if(parent->left == current)
            {
                parent->left = current->left;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
            else
            {
                parent->right = current->left;
                cout << "The value " << value << " was removed." << endl;
                delete current;
            }
        }
        return;
    }

    //Node with 2 children - Replace node with smallest value in right subtree.
    if (current->left != NULL && current->right != NULL)
    {
        BTNode<T>* check;
        check = current->right;
        if((check->left == NULL) && (check->right == NULL))
        {
            current = check;
            delete check;
            current->right = NULL;
            cout << "The value " << value << " was removed." << endl;
        }
        else // right child has children
        {
            //if the node's right child has a left child; Move all the way down left to locate smallest element
            if((current->right)->left != NULL)
            {
                BTNode<T>* leftCurrent;
                BTNode<T>* leftParent;
                leftParent = current->right;
                leftCurrent = (current->right)->left;
                while(leftCurrent->left != NULL)
                {
                    leftParent = leftCurrent;
                    leftCurrent = leftCurrent->left;
                }
                current->data = leftCurrent->data;
                delete leftCurrent;
                leftParent->left = NULL;
                cout << "The value " << value << " was removed." << endl;
            }
            else
            {
                BTNode<T>* temp;
                temp = current->right;
                current->data = temp->data;
                current->right = temp->right;
                delete temp;
                cout << "The value " << value << " was removed." << endl;
            }
        }
        return;
    }
}

/*
    Print out the values in the tree and their
    relationships visually.  Sample output:

                        22
                18
        15
10
                9
        5
                3
                        1
*/
template <typename T>
void BST<T>::print() const
{
    print(root,0);
}

template <typename T>
void BST<T>::print(BTNode<T>* node,int depth) const
{
    if(node == NULL)
    {
        std::cout << std::endl;
        return;
    }

    print(node->right,depth+1);
    for(int i=0; i < depth; i++)
    {
        std::cout << "\t";
    }
    std::cout << node->data << std::endl;
    print(node->left,depth+1);
}

#endif

Thanks again.