Segmentation fault (core dumped) while creating binary tree of given height

Question

This is my first time working with trees. I wrote a c++ code, but it says Segmentation fault (core dumped) , As far as I searched, this error comes from accessing a memory location that may be NULL. I tried 'new' keyword as malloc() should be avoided in c++, But still I didn't get how to resolve this in my code.

# include<iostream>
using namespace std;
struct node
{
    int data;
    node *left;
    node *right;
}*next;

int k=0;

void tree(int i,/*struct*/ node *next = new node)
{
  ++k; --i;
  if (i==0)
    return;
  //next = new node;
  next->data = k*k;
  next->left = NULL;
  next->right = NULL;
  tree(i, next->left);
  tree(i, next->right);
  return ;
 }

 void display (node* next)
 {
  cout<<next->data<<" ";
  if (next->left!=NULL)
    {
        display(next->left);
        display(next->right);
    }
 }
 int main()
 {
   int h;
   cout<<"Enter the expected height of tree : ";
   cin>>h;
   node *root;
   root = new node;
   root->data=0;
   root->left=NULL;
   root->right=NULL;
   tree(h, (root->left));
   tree(h, (root->right));
   cout<<root->data<<" ";
   display(root->left);
   display(root->right);
   return 0;
 }

What input are you giving to the program, i.e., what is the initial value of h? — Abhishek Bansal
– Abhishek Bansal, Commented Jun 8, 2014 at 11:02
Any integer. Even if cout/cin statements are replaced by h=3; i.e. may be any constant, still Segmentation fault exists — Piyush Deshmukh
– Piyush Deshmukh, Commented Jun 8, 2014 at 11:04

Beta · Accepted Answer · 2014-06-08 11:35:42Z

1

There are serious problems with this code. In particular, here:

void display (node* next)
{
  cout<<next->data<<" ";
  if (next->left!=NULL)
  {
    ...
  }
}

You dereference next without ever checking to see whether it's null. And it will be null. That's enough to explain the error you see.

I say that it will be null because of this:

void tree(int i,/*struct*/ node *next = new node)
{
  ...
  return ;
}

...
root->left=NULL;
...
tree(h, (root->left));
...
display(root->left);

The tree function takes its second argument by value-- that means that it does not change the value of root->left. You then call display with a null argument. I suspect that you think void tree(int i,/*struct*/ node *next = new node) means something other than what it actually means.

More fundamentally, you must review the two ways to pass an argument, by reference and by value.

More fundamentally still, you must start with a small, simple program and build up in small steps, rather than trying to write a big complex program all at once.

edited Jun 8, 2014 at 11:35

answered Jun 8, 2014 at 11:21

Beta

99.5k18 gold badges159 silver badges156 bronze badges

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

1 Comment

Piyush Deshmukh Over a year ago

Yes I was wrong, I should have passed arguments by reference and not by value.

emil · Accepted Answer · 2014-06-08 11:29:21Z

0

#include <iostream>

using namespace std;

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

void tree(int i, struct node **root, int k)
{
    if (i < 1)
        return;

    *root = new struct node;
    (*root)->data = k*k;
    (*root)->left = NULL;
    (*root)->right = NULL;
    tree(i - 1, &((*root)->left), k + 1);
    tree(i - 1, &((*root)->right), k + 1);
}

void display(struct node *root)
{
    if (root == NULL)
        return;
    cout << root->data << " ";
    if (root->left != NULL) 
        display(root->left);
    if (root->right != NULL)
        display(root->right);
}

int main()
{
    struct node *root;
    int h;

    cout<<"Enter the expected height of tree : ";
    cin>>h;
    tree(h, &root, 0);
    display(root);
    return 0;
}

I think you should do some more read up on how pointers works: http://www.tutorialspoint.com/cprogramming/c_pointers.htm

When you where calling tree(h, root->left) you actually just send the pointers value "NULL" == 0x0. As you want to allocate memory for it you should send a reference to the pointer. Hence &root and &((*root)->left). In the display function you have to check for NULL values both for left and right.

The code above is only improved and doesn't handle any freeing of memory, to be able to do that, traverse the tree and use delete on all leafs and work you back to the root.

answered Jun 8, 2014 at 11:29

emil

1,70013 silver badges12 bronze badges

1 Comment

Piyush Deshmukh Over a year ago

I should have passed parameters by reference. And that's why you always passed address of current node.Learnt a new thing, pointer to a pointer. Thanks.

Collectives™ on Stack Overflow

Segmentation fault (core dumped) while creating binary tree of given height

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related