CODEWITHSUNDEEP
c++segmentation-fault
Kenil Patel
Kenil Patel

Reputation: 105

Why does this code gives segmentation fault?

I am implementing the following algorithm :

1.Create an empty queue.

2.Make the first node of the list as root, and enqueue it to the queue.

3.Until we reach the end of the list, do the following.

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;

struct Node{
    int data;
    struct Node* next;
};

typedef struct Node* NODE;

NODE createNode(int data){
    NODE newNode = (NODE) malloc (sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return (newNode);
}

void insertAtEnd(NODE* head, int data){
    NODE newNode = createNode(data);
    if(*head == NULL){
        *head = newNode;
        return ;
    }

    NODE temp = *head;
    while(temp->next){
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = NULL;
    return;
}


struct tree_node{
    int data;
    struct tree_node* left;
    struct tree_node* right;
};

typedef struct tree_node* T_NODE;

T_NODE createTreeNode(int data){
    T_NODE newNode = new tree_node;
    newNode->right = NULL;
    newNode->left = NULL;
    newNode->data = data;
    return newNode;
}

void inorderTraversal(){}


T_NODE convertListIntoCBT(NODE head){


    T_NODE root;

    if(head){
        queue<T_NODE>q;
        root=createTreeNode(head->data);

        if(!root){
            cout << "Error creating root"<<endl;
            exit(-1);
        }
        q.push(root);

        T_NODE temp=NULL , parent=NULL;
        while(head->next){
            temp = q.front();
            q.pop();
            parent = temp;
            head = head->next;
            parent->left = createTreeNode(head->data);
            q.push(parent->left);
            head = head->next;
            parent->right = createTreeNode(head->data);
            q.push(parent->right);
        }

        return root;
    }
}

int main(){

    NODE head = NULL;
    insertAtEnd(&head,36);
    insertAtEnd(&head,30);
    insertAtEnd(&head,25);
    insertAtEnd(&head,15);
    insertAtEnd(&head,12);
    insertAtEnd(&head,10);

    //convert the given linked list into complete binary tree
    T_NODE new_root = convertListIntoCBT(head);

    return 0;
}

I tried debugging using gdb and i got the following result:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400e5a in convertListIntoCBT(Node*) ()
(gdb) backtrace
0  0x0000000000400e5a in convertListIntoCBT(Node*) ()
1  0x0000000000400fa2 in main ()
(gdb)

I am not able to figure as why am i getting the segmentation fault in the beginning of the function!?

Upvotes: 1

Views: 366

Answers (4)

A.S.H
A.S.H

Reputation: 29332

It seems that there's some missing checks in your while(head->next) loop. I think you should place a check to both next and next-to-next because you are using both in the loop:

while(head->next && head->next->next)
{
    //...
}

Or possibly check again before advancing a second time inside the loop:

    while(head->next){
        temp = q.front();
        q.pop();
        parent = temp;
        head = head->next;
        parent->left = createTreeNode(head->data);
        q.push(parent->left);

        if(head->next) // <-- check again here
        {
            head = head->next;
            parent->right = createTreeNode(head->data);
            q.push(parent->right);
        }
    }

Also as advised in the comments, dont mix C style with C++ style, choose one language and try to stick to it. I am talking here about using malloc and typedef struct, although they compile, they're not "usual" C++.

Upvotes: 1

Paul
Paul

Reputation: 13238

When built with -g you should have debuggable binary:

% lldb 1
(lldb) target create "1"
Current executable set to '1' (x86_64).
(lldb) r
Process 44386 launched: '/Users/paul/src/cpp/1' (x86_64)
Process 44386 stopped
* thread #1: tid = 0xb6153, 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81
   78                                   parent->left = createTreeNode(head->data);
   79                                   q.push(parent->left);
   80                                   head = head->next;
-> 81                                   parent->right = createTreeNode(head->data);
   82                                   q.push(parent->right);
   83                           }
   84
(lldb) bt
* thread #1: tid = 0xb6153, 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81
    frame #1: 0x0000000100001484 1`main + 116 at 1.cpp:100
    frame #2: 0x00007fff9cffe5ad libdyld.dylib`start + 1
    frame #3: 0x00007fff9cffe5ad libdyld.dylib`start + 1
(lldb) p parent
(T_NODE) $0 = 0x0000000100300320
(lldb) p head
(NODE) $1 = 0x0000000000000000

So in line 80 you make you head be nullptr by doing head = head->next. In line 81 you access head->data while head == nullptr getting your segfault.

Upvotes: 1

lazyplayer
lazyplayer

Reputation: 393

As other answers stated, the problem lies in the while statement.

Another problem in function convertListIntoCBT is that it has no return if head == nullptr.

Upvotes: 1

JeremiahB
JeremiahB

Reputation: 916

The key error is this piece of code:

while(head->next){
    temp = q.front();
    q.pop();
    parent = temp;
    head = head->next;
    parent->left = createTreeNode(head->data);
    q.push(parent->left);
    head = head->next;
    parent->right = createTreeNode(head->data);
    q.push(parent->right);
}

The last three lines are repeated without checking whether head is NULL or not. In this case the list comes to an end before the function is expecting it to and the program crashes by attempting to dereference a nullptr. Adding a check to convertListIntoCBT and aborting works, or you could build a way of enforcing having the correct number of elements in the list into the function insertAtHead.

Upvotes: 0

Related Questions