Segmentation Fault after building Binary Tree in C++

Question

I've built a binary tree in c++. After the tree has been built, I get a segmentation fault. Not sure why.

void buildTree(binTreeNode * r, int i){
    if(i > 0)
    {
        if(r != NULL)
        {
        if(r->left == NULL)
        {
            r->left = new struct binTreeNode;
            r->left->item = r->item + 1;
        }
        if(r->right == NULL)
        {
            r->right = new struct binTreeNode;
            r->right->item = r ->item + 1;

        }
        }
        i--;
        buildTree(r->left, i);
        buildTree(r->right, i);
    }
    return;
}

I set the initial id to 1 in main

"I get a segmentation fault. Not sure why." -- You may want to read these two links: 1. [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) 2. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) — Andreas Wenzel, Aug 01 '20 at 02:06
Please provide a [mre] which calls this function and reliably produces a segmentation fault. — Andreas Wenzel, Aug 01 '20 at 02:09

score 2 · Accepted Answer · answered Aug 01 '20 at 02:29

The problem is very likely due to your initialisation of the struct binTreeNode instances. Unlike languages such as Java or Python, C++ does not always initialise all attributes/members to zero, but rather depends on semantics when to do it.

So, what is happening under the hood? When you call new your_type;, the operating system hands you a piece of memory. The only guarantee you get, is that the allocated memory is at least the size of your_type. If you're (very¹⁰) lucky, the piece of memory is set to zero. It is more likely, however, that this piece of memory was previously used (and freed) by another process, which wrote to it. Thus it contains random data.

In practice, this means, that binTreeNode->left MIGHT be NULL, but this is not guaranteed. Same goes for binTreeNode->right.

How to fix:

Define a constructor, that explicitly sets the initial values of your instance. For your case, something like this should be sufficient:

struct binTreeNode {
    int id;
    binTreeNode* left;
    binTreeNode* right;

    binTreeNode()
    : id{0}
    , left{NULL}
    , right{NULL}
    {}
};

If you never heard of constructors (just in case): Constructors are special methods, which are called when creating a new instance of a type.

As a additional side note, instead of NULL use nullptr, which was introduced in C++11.

I'd suggest to declare a default parameter to the constructor: `binTreeNode(int _id=0) : id{0} , left{NULL} , right{NULL} {}` so that the object's value can be defined within a call to construction: `new binTreeNode(r->id+1);` — CiaPan, Aug 01 '20 at 15:34
Whoops, of course I meant `binTreeNode(int _id=0) : id{_id} , left{NULL} , right{NULL} {}` — CiaPan, Aug 01 '20 at 15:49
I think you meant to say `binTreeNode(int id=0) : id{id}, ...`. The underscore is unnecessary here. :-) — Julian Kirsch, Aug 01 '20 at 19:00

Andreas Wenzel · Answer 2 · 2020-08-01T02:41:42.827

The reason that you are experiencing a segmentation fault is probably that when you create a new node, you only initialize its data member id, but not its other two data members left and right. Therefore, these two pointers will be wild pointers when you call buildTree on this new node. Any attempt to dereference a wild pointer will likely cause a segmentation fault.

This answer assumes that binTreeNode is a simple C-style struct. If it is a class with a constructor which initializes all of its data members, then this answer is incorrect. Since you did not post the definition of binTreeNode, it is impossible for me to know.

Segmentation Fault after building Binary Tree in C++

2 Answers2