Binary Search Tree insert causing a stack overflow C++

Question

I am trying to insert values into a binary search tree. I have a class for the leaves of the tree, and a class for the collection itself. Here is the class for the leaves:

template <class K, class T>
class BSTLeaf{
public:
    BSTLeaf(const K& k, const T& c);
    K key;
    T data;
    BSTLeaf * left;
    BSTLeaf * right;
    void insert(const K& k, const T& c);
private:
};

Here is the insert function for the other class that is working as intended:

template <class K,class T>
void BSTKeyedCollection<K,T>::insert(const K& k, const T& c){
    if(root != NULL){
        cout << "trying to insert " << c << endl;
        root->insert(k,c);
    }
    else{
        cout << "ROOT WAS NULL" << endl;
        root = new BSTLeaf<K,T>(k,c);
        cout << "The root node contains " << c << endl;
    }
}

Here is the function that is causing the overflow:

template <class K, class T>
void BSTLeaf<K,T>::insert(const K& k, const T& c){
    //if the key is less than the node it comes to
    if(k < key){
        if(left == NULL){
            left = new BSTLeaf<K,T>(k,c);
        }
        else
            insert(k,c);
    }
    if(k > key){
        if(right == NULL){
            right = new BSTLeaf<K,T>(k,c);
        }
        else
            insert(k,c);
    }

}

Not sure if the constructor would be helpful but here it is:

template <class K,class T>
BSTLeaf<K,T>::BSTLeaf(const K& k, const T& c){
    key = k;
    data = c;
    left = NULL;
    right = NULL;
};

We are allowed to assume that K will always be a type that < and > will work for so that is not an issue. The function will insert a value at the root, insert one more value, and then overflow. Thanks in advance for the help!

So stop calling insert with the exact same parameters with which it was already called and on the exact same node... — Dark Falcon
– Dark Falcon, Commented Apr 8, 2015 at 19:22
Pardon my naivete, but why do your leaf pages have pointers? — Thomas Matthews
– Thomas Matthews, Commented Apr 8, 2015 at 19:26
@DarkFalcon would putting left = left->left and right = right->right before calling the function again be an efficient solution? — user3483203
– user3483203, Commented Apr 8, 2015 at 19:26

Jérôme · Accepted Answer · 2015-04-08 19:26:41Z

2

Looks like your problem is coming from the recursive call to insert. You should call it on the right or left leaf of the current leaf:

template <class K, class T>
void BSTLeaf<K,T>::insert(const K& k, const T& c){
    //if the key is less than the node it comes to
    if(k < key){
        if(left == NULL){
            left = new BSTLeaf<K,T>(k,c);
        }
        else
            left->insert(k,c);
    }
    if(k > key){
        if(right == NULL){
            right = new BSTLeaf<K,T>(k,c);
        }
        else
            right->insert(k,c);
    }

}

answered Apr 8, 2015 at 19:26

Jérôme

8,0764 gold badges34 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

James Wilkins · Accepted Answer · 2015-04-08 19:29:00Z

2

You are calling the same function on the same instance you are in, causing a stack overflow (cyclical calls to the same function). I think you meant left->insert(k,c); and right->insert(k,c);.

edited Apr 8, 2015 at 19:29

answered Apr 8, 2015 at 19:25

James Wilkins

7,5584 gold badges55 silver badges81 bronze badges

Collectives™ on Stack Overflow

Binary Search Tree insert causing a stack overflow C++

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related