Segmentation fault when setting up binary tree in C

Question

I picked up some ideas from this website: http://www.cprogramming.com/tutorial/c/lesson18.html

Then I wrote some code to create a binary tree. It is as follows

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  int key_value;
  struct node *left;
  struct node *right;
} node;

void createTree(node * leaf, int depth) {
  leaf->key_value = depth;
  if (depth == 0)  {
    leaf->left = 0;
    leaf->right = 0;
  } else {
    leaf->left = (node *) malloc(sizeof(node));
    leaf->right = (node *) malloc(sizeof(node));
  }
  createTree(leaf->left, depth - 1);
  createTree(leaf->right, depth - 1);
}

int main() {
  node head;
  createTree(&head, 3);
  (head.left)->key_value = 5;
  printf("%d\n", head.left->key_value);
  return 0;
}

It compiles just fine but when I run it I get a segmentation fault error. The idea is to start with a node called head, and then give that value 3, then give its two children value 2, etcetera and until we get to depth == 0, at which point we dont make any more leafs.

`if (depth == 0) { leaf->left = 0; leaf->right = 0; } else {` -->> `if (depth == 0) { leaf->left = 0; leaf->right = 0; return; } else {` BTW: and of course you don't need the else after the return. — wildplasser, Oct 28 '15 at 20:00
Be carefoul with ` (head.left)->key_value = 5;` , it could segfault if you create a tree of 0 depth, I advise to only nodes when creating them or after checking their existence. By the way [Please don't cast the return of malloc](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858#605858) — Kotshi, Oct 28 '15 at 20:16

score 2 · Answer 1 · answered Oct 28 '15 at 20:04

You have infinite recursion, as you don't return on depth == 0, but recurse on createTree again.

void createTree(node * leaf, int depth) {
    leaf->key_value = depth;
    if (depth == 0)  {
        leaf->left = 0;
        leaf->right = 0;
        return;
    }
    leaf->left = malloc(sizeof(node));
    leaf->right = malloc(sizeof(node));
    createTree(leaf->left, depth - 1);
    createTree(leaf->right, depth - 1);
}

score 2 · Accepted Answer · answered Oct 28 '15 at 20:05

2

Its an infinite recursion, there must always be something to return at base condition to get out of recursive loop:

if (depth == 0)  {
        leaf->left = 0;
        leaf->right = 0;
        return;   // edit
    }

answered Oct 28 '15 at 20:05

wrangler

3,454
1
19
28

Segmentation fault when setting up binary tree in C

2 Answers2