Tyler V
Tyler V

Reputation: 29

Binary Search Tree recursive insertion causing stack overflows, iterative insertion not working

I have this project to do for class where I have to add 10000 elements (in order) to a binary search tree -- among other things, but that's not what's currently broken. My recursive insertion works fine until about 3500 elements, then it breaks and causes a stack overflow. I then tried to create an iterative version of the code, but it only added element 9999 and 10000. So my questions:

How do I make my recursive insertion work for large amounts of sorted elements? Or how do I make my iterative insertion work at all?

My code is here:

Recursive:

template <typename T>
void BST<T>::insert(BST_Node<T>*& node, const T& data)
{
    if (node == NULL)
    {
        node = new BST_Node<T>(data);
        return;
    }

    if (node->mData == data)
    {
        cout << "Node already exists!" << endl;
        return;
    }

    if (data < node->mData)
        insert(node->mLeft, data);
    else
        insert(node->mRight, data);
}

Iterative:

template <typename T>
void BST<T>::insertIterative(BST_Node<T>*& node, const T& data)
{
    if (node == NULL)
    {
        node = new BST_Node<T>(data);
        return;
    }    

    while (node != NULL)
    {
        if (data < node->mData)
        {
            if (node->mLeft == NULL)
            {
            node->mLeft = new BST_Node<T>(data);
            return;
        }
        else
            node = node->mLeft;
    }
    else if (data > node->mData)
    {
        if (node->mRight == NULL)
        {
            node->mRight = new BST_Node<T>(data);
            return;
        }
        else
            node = node->mRight;
    }
}

Also, here's my public insert function if necessary:

template <typename T>
void BST<T>::insert(T data)
{
    insert(mRootNode, data); //insertIterative(mRootNode, data);
}

And finally, here's the error I get when my recursive code breaks:

Unhandled exception at 0x7717CF87 (ntdll.dll) in PA7.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x006F2FF0).

My BST_Node constructors:

template <typename T>
struct BST_Node
{
    T           mData;
    BST_Node<T> *mLeft, *mRight;

    BST_Node();
    BST_Node(T data);
    BST_Node(T data, BST_Node<T> *left, BST_Node<T> *right);
};

template <typename T>
BST_Node<T>::BST_Node()
{
    mData = 0;
    mLeft = NULL;
    mRight = NULL;
}

template <typename T>
BST_Node<T>::BST_Node(T data)
{
    mData = data;
    mLeft = NULL;
    mRight = NULL;
}

template <typename T>
BST_Node<T>::BST_Node(T data, BST_Node<T> *left, BST_Node<T> *right)
{
    mData = data;
    mLeft = left;
    mRight = right;
}

BST constructors:

template <typename T>
BST<T>::BST()
{
    mRootNode = NULL;
}

template <typename T>
BST<T>::BST(T data, BST_Node<T> *left, BST_Node<T> *right)
{
    mRootNode->mLeft = left;
    mRootNode->mRight = right;
    mRootNode->mData = data;
}

Upvotes: 1

Views: 595

Answers (1)

Nicolas Chabanovsky
Nicolas Chabanovsky

Reputation: 268

The problem could be because tree isn't balanced. This means that in worst case the call stack will contain the same number of function calls as the number of items in the tree. After each insert you should check balance of the tree and if it is necessary to correct it.

Also you could divide the insert function on:

  1. Find a node which will be parent
  2. Add new node

Then optimise the find function (just google "leftmost"/"rightmost").

Upvotes: 3

Related Questions