Binary tree insertion method causes stack overflow

Question

The problem

I'm having some doubts with my insertion method in C++, it causes a stack overflow.

Compiled with g++ on Windows

g++ -Wall -O2 Tree.cpp -o Tree

Output

0 [unknown (0x2B70)] Tree 10496 cygwin_exception::open_stackdumpfile: Dumping stack trace to Tree.exe.stackdump

Code

# include < iostream >

using namespace std;

struct Node{

    int val;
    Node *left, *right;

};

Node* Insert(Node *node, int val)
{

    if(node == NULL)
    {
        node = new Node;
        node->val = val;
        node->right = node->left = NULL;
    }   

if(node->val > val)
    node->left = Insert(node->left, val);
else
    node->right = Insert(node->right, val);

return node;

}

int main()
{

Node *root = NULL; // New tree

root = Insert(root, 5);
root = Insert(root, 19);
root = Insert(root, 1);
root = Insert(root, 32);
return 0;
}

This is because return node should be added to the if for the base case. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Jul 22, 2016 at 16:16

MikeCAT · Accepted Answer · 2016-07-22 16:15:12Z

2

You have to stop recursion when it reached to NULL.

Try this:

Node* Insert(Node *node, int val)
{

    if(node == NULL)
    {
        node = new Node;
        node->val = val;
        node->right = node->left = NULL;
    }

    else if(node->val > val) // add "else" here
        node->left = Insert(node->left, val);
    else
        node->right = Insert(node->right, val);

    return node;

}

answered Jul 22, 2016 at 16:15

MikeCAT

75.1k11 gold badges50 silver badges71 bronze badges

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

1 Comment

Bit87 Over a year ago

Wow, Now it works, I'm new in recursion :), Thanks for your time.

rj99999 · Accepted Answer · 2016-07-22 17:23:00Z

0

The problem in your function is, you are trying to access null memory. 
Please check my comments here

/* You are checking for node == null, which is correct. */
if(node == NULL)
    {
        node = new Node;
        node->val = val;
        node->right = node->left = NULL;
    }


    /* Consider what will happen when node is null, you are still trying to access null memory. You need to put else if here to avoid control to fall into this condition if node is null. */
    if(node->val > val) // add "else" here
        node->left = Insert(node->left, val);
    else
        node->right = Insert(node->right, val);

answered Jul 22, 2016 at 17:23

rj99999

10911 bronze badges

1 Comment

Bit87 Over a year ago

Thanks for explaining , recursion is a bit confusing at the beginning, this condition apply in all the recursive methods? For example, count the number of nodes.

Collectives™ on Stack Overflow

Binary tree insertion method causes stack overflow

The problem

Compiled with g++ on Windows

Output

Code

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

The problem

Compiled with g++ on Windows

Output

Code

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related