C binary tree segfault (implementation with class)-CodePudding

I've been trying to implement BST in c and I wrote these functions to insert new nodes in it. However, I am now quite stuck trying to understand why this code causes segfault.

It probably has something to do with the fact that I'm not passing the address of root to my utility function because when I do, the insert functions start working properly. However, I do not understand why this particular implementation does not work. I would really appreciate if someone could clarify

class Bst {
    private:
        struct bstNode *root;
        struct bstNode* insertUtil(int, struct bstNode*);
        void delTree(struct bstNode**);
    public:
        Bst();
        ~Bst();
        void insert(int);
};

 /// struct bstNode *root = NULL;

struct bstNode* Bst::insertUtil(int x, struct bstNode *r){
    if(r == NULL){
        r = newNode(x);
    }
    if(x < r->data){
        r->left = insertUtil(x, r->left);
    } else{
        r->right = insertUtil(x, r->right);
    }
    return r;
}

void Bst::insert(int x){
    if(root == NULL){
        root = newNode(x);
        return;
    }
    insertUtil(x, root);
}

full code if you're interested: https://codepen.io/adrasti/pen/NWyVOZY

CodePudding user response：

I think it's a logic error.

this line(in insertUtil):

r = newNode(x); //no return

So, program will execute

insertUtil(x, r->left);

r->right = insertUtil(x, r->right);

and will alway execute:

r = newNode(x); //no return

never stop until out of memory.

I am also learning C , and I hope to be corrected if I am not correct.

CodePudding user response：

Definetly you miss break condition in Bst::insertUtill you can quickly by making small refactor in that function

struct bstNode *Bst::insertUtil(int x, struct bstNode *r)
{
  if (r == nullptr)
  {
    r = newNode(x);
    return nullptr;
  }
  if (x < r->data)
  {
    r->left = insertUtil(x, r->left);
  }
  else
  {
    r->right = insertUtil(x, r->right);
  }
  return r;
}

and after that change Bst::insert to

void Bst::insert(int x)
{
  insertUtil(x, root);
}

by doing that you will avoid stack overflow.

In case of searching of that you can add -fsanitize=address flag to gcc compiler or user valgrind

Also you can refactor code to be more C modern style but that I can paste you later