Stack Overflow when inserting a node in a Binary Search Tree

-3

I am new to programming in C++ but I am trying to create a Binary Search Tree.

The program seems to compile fine but it gives me this error:

 Unhandled exception at 0x009229B7 in Lab001_CS3.exe: 0xC00000FD: Stack 
 overflow (parameters: 0x00000001, 0x00AD2FBC).

when I try to run it. The error occurs on this line of code:

void insert(int value) {
   ...
}

I am not sure what I am doing wrong, and I have never gotten this error before.

Here is the code:

#include <iostream>

using namespace std;

//create a node struct
struct node {

    //member variables
    int key;
    node* left;
    node* right;

    //default constructor
    node() {
        key = 0;
        left = NULL;
        right = NULL;
        cout << "a new node is created" << endl;
    }

    //constructor so can create a node in one line
    node(int k) {
        key = k;
        left = NULL;
        right = NULL;
        cout << "a new node is created" << endl;
    }


};

class Tree {
public:
    //root node
    node root;

    //default constructor 
    Tree() {
        root.key = 0;
        root.left = NULL;
        root.right = NULL;


    }

    //constructor to create the root node
    Tree(int data) {

        //set the data to the key
        //set the right and left pointers to null
        root.key = data;
        root.left = NULL;
        root.right = NULL;
    }

    //print the root node
    void printRootNode() {
        cout << "Root Node - Key: " << root.key << endl;
    }

    //insert functions
    void insert(int value) {

        /* If the newNode's key is less than the root key, traverse left 
    */
    if (value < root.key) {

        /* if the left node is NULL */
        if (root.left == NULL) {
            root.left = new node(value);
            cout << "assigned left" << endl;
        }
        else {

            /* if the left node is important */
            insert(value);
            cout << "recurse" << endl;
        }

    }

    if (value > root.key) {

        /* if the right node is NULL */
        if (root.right == NULL) {
            root.right = new node(value);
            cout << "assigned right" << endl;
        }
        else {
            /* if the right node is important */
            insert(value);
            cout << "recurse" << endl;
        }
    }
}


};

//print inorder
void inorder(node* rt) {
//base
if (rt == NULL) {
    return;
}

inorder(rt->left);
cout << " " << rt->key << endl;
inorder(rt->right);
}

int main() {

//create a tree for a root node
Tree t(16);
t.printRootNode();

//create  newNode
node n1(20);
node n2(31);

//insert the new nodes
t.insert(20);
t.insert(31);

//keep the window from closing
system("pause");
}

Thank you for any help.

c++
data-structures
binary-tree
binary-search-tree
asked on Stack Overflow Jul 6, 2019 by Ikechukwu Anude • edited Jul 6, 2019 by Jonathan Leffler

1 Answer

1

In your insert()

if (value < root.key) {

        /* if the left node is NULL */
        if (root.left == NULL) {
            root.left = new node(value);
            cout << "assigned left" << endl;
        }
        else {

            /* if the left node is important */
            insert(value);
            cout << "recurse" << endl;
        }

    }

let's take this go left snippet as example, if root.left != NULL the code will enter else block and recursively call insert(value) forever, which cause stack overflow, the correct operation is make current node move to root.left, and then call insert(value) recursively.

also you don't need node class at all, tree class can do all the things.

again, here is not a good place for help you debug, you need to learn how to do this yourself :-).

answered on Stack Overflow Jul 6, 2019 by Xinlin Feng

User contributions licensed under CC BY-SA 3.0