Segmentation fault while building binary search tree

Question

I am building a binary search tree, but the function is giving segmentation fault. I don't know where is the problem.

The tree doesn't build the part in the insertintree does not work properly and I have tried ways but it is not working

#include<bits/stdc++.h>
using namespace std;

struct node // structure of node
{
    int k;
    node* left = NULL;
    node* right = NULL;
};    
void insertintree(node* root, int key)
{
    if (root == NULL)//root addition
    {
        node* root = new node;
        root->k = key;
    }
    else 
    {
        if (root->k < key)  insertintree(root->right, key);
        else insertintree(root->left, key);
    }
}    
void inorder(node* root) 
{
    if (root != NULL) 
    {
        inorder(root->left);
        cout << root->k;
        inorder(root->right);
    }
}    
int main() 
{
    node* root = NULL;
    insertintree(root, 1);
    cout << root->k;
}

You need to pass by reference: `void insertintree(node*& root,int key)` — πάντα ῥεῖ, Jun 21 '19 at 12:00
I feel like I saw this exact question the other day. Anyway, the problem is you're not passing by reference. — , Jun 21 '19 at 12:06
As @ThomasSablik said, use debugger to avoid "i don't know where is the problem" situation. This helps finding problem by yourself, as well as asking question on SO, if need arises. — Gaurav Singh, Jun 21 '19 at 12:06

JeJo · Answer 1 · 2019-06-21T12:25:33.583

3

You have mainly two issues:

You need to pass the root by reference, otherwise, insertintree will work with a copy of the root you pass.
```
void insertintree(node* &root, int key)
//                     ^^^
{

}
```
secondly, in your first if's body, you have re-declared a new root Node which will shadow the passed one. change to
```
if (root == NULL)//root addition    
{
     root = new node;
     root->k = key;
}
```

Also avoid practicing with #include<bits/stdc++.h> and using namespace std;: Why? See the following discusssiions:

edited Jun 21 '19 at 12:25

answered Jun 21 '19 at 12:12

JeJo

30,635
6
49
88

`insertintree will work with the copy of the root you pass` sounds like it is the same copy which is being passed. I think one should better say `insertintree makes a new copy of root you pass`. Or change `with the copy` to `with a copy` – Gaurav Singh Jun 21 '19 at 12:18

john · Answer 2 · 2019-06-21T12:21:36.140

There's multiple problems with your code. The first is that you redeclare root.

void insertintree(node* root,int key) // root declared here
{
    if(root==NULL)
    {
        node* root = new node; // root redeclared here

These are two different variables (even though they have the same name). You should have written this

void insertintree(node* root, int key) // root declared once
{
    if(root==NULL)
    {
        root = new node; // now this is the root declared above

The second problem is that you are expecting the intsertintree function to change the root declared in main but it doesn't. Again just because two variables have the same name doesn't mean they are the same variable.

void insertintree(node* root,int key) // a variable called root
{
     ...
}

int main()
{
     node* root = NULL; // another variable called root
     ...
}

Changing the root variable in insertintree has no effect at all on the variable called root in main, they are different variables.

To make this work you have to pass by reference. When a variable is a reference then changes to it change the variable being refered to. Change your insertintree function like this

void insertintree(node*& root,int key)
                    // ^ this makes root a reference
{

Now root is a reference to the variable in main and changes to it will also change the variable in main.

And in the same way, when your recursively call insertintree like this

insertintree(root->right,key);

the insertintree function is going to be able to change root->right because it takes a reference to root->right.

Segmentation fault while building binary search tree

2 Answers2