Pointer trouble creating binary trees

Question

I am creating a binary tree from a bitstring in c. ie 1100100 creates a tree:

  1
 / \
1   1

I decided to use a recursive function to build this tree however i keep getting the error Debug assertion failed... Expression : CrtIsValidHeapPointer(pUserData)

here is a fragment of my code

typedef
struct Node {
  char key;
  struct Node *left;
  struct Node *right; 
} Node;

char string[1000];
int i = 0;

void insertRecursivePreorder(Node **node)
{
    Node* parent = *node;
    if(string[i] == '0')
    {
        parent = NULL;
        i++;
    }
    else
    {
        Node *newn = (Node*)malloc(sizeof(Node));
        newn->key = string[i];
        parent = newn;
        i++;
        insertRecursivePreorder(&newn->left); //errors occur here
        insertRecursivePreorder(&newn->right); //errors occur here
        free(newn);
        free(parent);
    }
}

int main(void)
{
    void printTree(Node* node);
    Node* root = NULL;
    scanf("%s", string);
    insertRecursivePreorder(&root);
    //... do other junk
}

i was wondering why this error comes about and what i can do to fix it.

yeap i have, i know where the errors occur but honestly using a recurrsive method means its really hard to debug because there are so many pointers and pointers to pointers etc — Wasiq Kashkari
– Wasiq Kashkari, Commented Apr 28, 2012 at 2:22
actually, i really want to know why i cannot insert &newn->right into my insertRecursivePreorder function — Wasiq Kashkari
– Wasiq Kashkari, Commented Apr 28, 2012 at 2:23
"i know where the errors occur" -> so how about giving us the stack trace? Also, have you tried valgrind? — smocking
– smocking, Commented Apr 28, 2012 at 2:38

huon · Accepted Answer · 2012-04-28 02:57:28Z

1

The immediate problem is likely to be calling free on a pointer twice. In insertRecursivePreorder, you set parent to newn, and then call free on both. As an example of this, the following program fails (but works if you comment out one of the free(..)s):

#include <stdlib.h>
int main() {
  int *a = malloc(sizeof(int)),
      *b = a;
  free(a);
  free(b);
  return 0;
}

However, there are several problems with your logic here. You should only call free when you have completely finished with the pointer, so if you are using your tree later you can't free it as you construct it. You should create a second function, recursiveDestroyTree, that goes through and calls free on the tree (from the bottom up!).

And, you probably want *node = newn rather than parent = newn, since the latter is the only one that actually modifies node.

(You could also change your function to return a Node * pointer, and then just go:

root = insertRecursivePreorder();

and

newn->left = insertRecursivePreorder();
newn->right = insertRecursivePreorder();

instead of trying to keep track of pointers to pointers etc.)

(Furthermore, on a stylistic point, using global variables is often bad practice, so you could have your insertRecursivePreorder take int i and char * string parameters and use them instead of global variables.)

edited Apr 28, 2012 at 2:57

answered Apr 28, 2012 at 2:39

huon

104k24 gold badges239 silver badges230 bronze badges

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

1 Comment

Wasiq Kashkari Over a year ago

OMG thanks so much!! figured it out!! sorry im only a second year soft eng student :P

wildplasser · Accepted Answer · 2012-04-28 12:37:01Z

The problem was: you were never assigning to the double pointer in 'insertRecursivePreorder', so root always stayed NULL.

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

typedef
struct Node {
  char key;
  struct Node *left;
  struct Node *right;
} Node;

        /* slightly changed the syntax for the str
        ** ; now '.' indicates a NULL pointer, values represent themselves.
        */
char *string = "12..3.." ;
/* Removed the global index 'i' */

void printTree(Node* node, int level);
unsigned insertRecursivePreorder(Node **pp, char *str);

unsigned insertRecursivePreorder(Node **pp, char *str)
{
    unsigned pos =1;
    if (!*str) { *pp = NULL; return 0; } /* safeguard for end of string */
    if (*str == '.') { *pp = NULL; return pos; }

    *pp  = malloc(sizeof **pp);
    (*pp)->key = *str;
    pos += insertRecursivePreorder(&(*pp)->left, str+pos);
    pos += insertRecursivePreorder(&(*pp)->right, str+pos);
    return pos;
}

void printTree(Node* node, int level)
{
unsigned pos,len;
len = level> 0 ? level : -level;

    for (pos =0; pos < len; pos++) putchar (' ');
    if (!level) printf ("Root=");
    else if (level<0) printf ("Left=");
    else printf ("Right=");
    if (!node) { printf( "Null\n" ); return; }
    printf("Key=%c\n", node->key );
    printTree(node->left, -(len+1) ) ;
    printTree(node->right, len+1) ;
}

int main(void)
{   
    Node *root = NULL;
    unsigned result = 0;
    result = insertRecursivePreorder(&root, string);
    printf( "Result=%u\n", result);
    printTree(root, 0);
    return 0; printTree(root, 0);
}

Output:

Result=7
Root=Key=1
 Left=Key=2
  Left=Null
  Right=Null
 Right=Key=3
  Left=Null
  Right=Null

Collectives™ on Stack Overflow

Pointer trouble creating binary trees

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related