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 2. What is a debugger and how can it help me diagnose problems? — Andreas Wenzel
– Andreas Wenzel, Commented Aug 1, 2020 at 2:06
Please provide a minimal reproducible example which calls this function and reliably produces a segmentation fault. — Andreas Wenzel
– Andreas Wenzel, Commented Aug 1, 2020 at 2:09

Julian Kirsch · Accepted Answer · 2020-08-01 02:29:03Z

2

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.

answered Aug 1, 2020 at 2:29

Julian Kirsch

7746 silver badges22 bronze badges

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

3 Comments

CiaPan Over a year ago

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 Over a year ago

Whoops, of course I meant binTreeNode(int _id=0) : id{_id} , left{NULL} , right{NULL} {}

Julian Kirsch Over a year ago

I think you meant to say binTreeNode(int id=0) : id{id}, .... The underscore is unnecessary here. :-)

Andreas Wenzel · Accepted Answer · 2020-08-01 02:41:42Z

1

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.

edited Aug 1, 2020 at 2:41

answered Aug 1, 2020 at 2:31

Andreas Wenzel

27.1k4 gold badges33 silver badges52 bronze badges

Collectives™ on Stack Overflow

Segmentation Fault after building Binary Tree in C++

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related