C++ binary tree segfault (implementation with class)

Question

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

*However, I am now quite stuck trying to understand why this code causes segfault.* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Jun 21 '22 at 13:52
Think some more about what happens after `r = newNode(x);` in `insertUtil`. — molbdnilo, Jun 21 '22 at 13:58
In C++, you don't need `struct` tagging each `bstNode` identifier type. — Eljay, Jun 21 '22 at 14:01
Here we miss a lot of code to give an answer... try to use a debugger — Marco Beninca, Jun 21 '22 at 14:46
You sometimes use the value `Bst::insertUtil` returns, and sometimes you don't. This is not healthy. Decide on one way to use a function, and apply it throughout the code. Why couldn't you write for example `void Bst::insert(int x){ root = insertUtil(x, root); }`? Or perhaps (a better interface) make `insertUtil` return `void` but accept `r` by reference? — n. m. could be an AI, Jun 21 '22 at 15:34
@n.1.8e9-where's-my-sharem. You’re right. I actually tried to write the “insert” function this way, but it doesn’t help to solve the issue. According to my limited understanding of how this code works, the one only way the “insertUtil” function returns anything other than the “root” itself is when is when I pass NULL as an argument to it. However, this case is covered by the “if” condition I have inside my “insert” function. Therefore, would it not be an extra assignment operation if I wrote it as in your example? — segugio, Jun 21 '22 at 17:10
@n.1.8e9-where's-my-sharem. As for the latter part of your suggestion, I actually did try to make “insertUtil” accept the reference and it does solve the issue, as I stated in the original question. However, I’m really racking my brain trying to understand why the code I showed doesn’t work — segugio, Jun 21 '22 at 17:12
@molbdnilo I create a new node with node->left and newnode->right equal to NULL and newnode->data equal to x and then pass its address to “r” inside “insertUtil”, right? Then this new address is being assigned to r->left or r->right from the previous function call, and all other function calls just repeat the already existing links in the tree… or so I think — segugio, Jun 21 '22 at 17:45
It is not going to solve your issue, which you need to address separately. Use a debugger. — n. m. could be an AI, Jun 21 '22 at 18:35
@segugio Why do you feel a need to insert anything into the empty subtrees of the newly created node? You already have anode with `x`, so your work must be done. (All you need to do to make it work is to insert `else` in one place.) — molbdnilo, Jun 21 '22 at 19:59

Yeonon · Answer 1 · 2022-06-21T15:07:43.547

1

I think it's a logic error.

this line(in insertUtil):

r = newNode(x); //no return

So, program will execute

insertUtil(x, r->left);

or

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.

edited Jun 21 '22 at 15:07

answered Jun 21 '22 at 15:06

Yeonon

21
3

You were almost there :) – Patryk Gawroński Jun 21 '22 at 15:56
Thank you for your answer. Could you please clarify why doesn’t “newNode“ have a return? Please note that “bstNode* newNode(int x)” is a function that I wrote, as can be seen if you go to the link to the full code I provided. I apologize I didn’t paste some parts of the code directly, I thought the question would be convoluted if I did – segugio Jun 21 '22 at 16:57
@segugio I saw the implementation of `newNode(int)` function. myaybe it's not clear enough for me to describe, I means after execute `newNode(x)` in insertUtil, should return.As Patryk Gawroński answered. – Yeonon Jun 22 '22 at 12:47

score 0 · Answer 2 · answered Jun 21 '22 at 15:55

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

Thank you for your answer. Please note that the problem that bothers me so is not a stack overflow, but a segmentation fault. I tried to implement the improvements you showed, but i think now the problem is that while a new node is being assigned to the variable “r” inside the “insertUtil” function, the “root” remains unchanged, since “r” is only a copy of root. Therefore, the “root” never actually changes and no new nodes are inserted in the tree — segugio, Jun 21 '22 at 16:50

C++ binary tree segfault (implementation with class)

2 Answers2