Segmentation fault on recursion function c++

Question

I was working on Pre-order traverse Binary Tree algorithm. But I meet with Segmentation fault:11 error. The codes are shown as follow.

I want to know why this error happens. By the way, I have tried non-recursion algorithm preorder()，segmentation fault still happen.

The environment: macOS, clang-800.0.38

struct Node{
    char val;
    Node* left;
    Node* right;
};

void preorder(Node *T){
    if(T!=NULL){
        cout << T->val;
        preorder(T->left);
        preorder(T->right);
    }
}

int main(){
    Node *T = (Node *)malloc(sizeof(Node));
    Node *p = T;
    p->val = 'A';
    p->left = (Node *)malloc(sizeof(Node));
    p->left->val = 'B';
    p->right = (Node *)malloc(sizeof(Node));
    p->right->val = 'C'; 
    preorder(T);
    return 0;
}

malloc won't zero-out the memory for you. Which means, the Node malloc-ed could have non-NULL left and right so your preorder() will incorrectly traverse into invalid memory location. As you are using C++, why don't you write a constructor for your class and use new, instead of using malloc ? — Adrian Shum
– Adrian Shum, Commented Mar 22, 2019 at 6:47
Both answers have pointed out the cause. You could do self-diagnosis here in the future: segfault.stensal.com/a/e4e7lMyfNQ62slZH — stensal
– stensal, Commented Mar 22, 2019 at 8:21

Daniel Langr · Accepted Answer · 2019-03-22 06:57:35Z

2

You need to initialize left and right member variables of your nodes to null pointers.

Anyway, if you use C++, use C++ and not C constructs. This is an exemplary C++14 version of your code:

#include <iostream>
#include <memory>

struct Node{
   Node(char a) : val(a) { };
   char val;
   std::unique_ptr<Node> left, right;
};

void preorder(Node* p) {
   if (p) {
      std::cout << p->val;
      preorder(p->left.get());
      preorder(p->right.get());
   }
}

int main() {
   auto root = std::make_unique<Node>('A');
   root->left = std::make_unique<Node>('B');
   root->right = std::make_unique<Node>('C');

   preorder(root.get());
}

edited Mar 22, 2019 at 6:57

answered Mar 22, 2019 at 6:46

Daniel Langr

24.2k3 gold badges55 silver badges110 bronze badges

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

2 Comments

skratchi.at Over a year ago

sry for asking, but isn't this plain c++11??

skratchi.at Over a year ago

being in the good position, to be able to use always the newest features. i lost track of the versions. thy for the answer =)

skratchi.at · Accepted Answer · 2019-03-22 10:18:01Z

The problem is left and right of your child nodes are not initialized to NULL. Due to previous value stored in that memory location the program is encountering non-null value in your if(T!=nullptr) statement and executing the if block.

struct Node{
    char val;
    Node* left;
    Node* right;
};

void preorder(Node *T){
    if(T!=nullptr){
        cout << T->val;
        preorder(T->left);
        preorder(T->right);
    }
}

int main(){
    Node *T = (Node *)malloc(sizeof(Node));
    Node *p = T;
    p->val = 'A';
    p->left = (Node *)malloc(sizeof(Node));
    p->left->val = 'B';
    p->left->left = nullptr;   //Initialize to NULL
    p->left->right = nullptr;  //Initialize to NULL
    p->right = (Node *)malloc(sizeof(Node));
    p->right->val = 'C'; 
    p->right->left = nullptr;  //Initialize to NULL
    p->right->right = nullptr; //Initialize to NULL
    preorder(T);
    return 0;
}

Collectives™ on Stack Overflow

Segmentation fault on recursion function c++

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related