Tree traversal - Segmentation fault error

Question

Code :

#include<stdio.h>
#include<malloc.h>

typedef struct tree
{
    char data;
    struct tree *left;
    struct tree *right;
}*pos;

pos stack[30];
int top=-1;

pos newnode(char b)
{ 
    pos temp;
    temp=(struct tree*)malloc(sizeof(struct tree));
    temp->data=b;
    temp->left=NULL;
    temp->right=NULL;
    return(temp);
}

void push(pos temp)
{
    stack[++top]=temp;
}

pos pop()
{
    pos p;
    p=stack[top--];
    return(p);
}

void inorder(pos t)
{
    if(t!=NULL)
    {
        inorder(t->left);
        printf("%s",t->data);
        inorder(t->right);
    }
}
void preorder(pos t)
{
    if(t!=NULL)
    {
        printf("%s",t->data);
        preorder(t->left);
        inorder(t->right);
    }
}

void postorder(pos t)
{
    if(t!=NULL)
    { 
        postorder(t->left);
        postorder(t->right);
        printf("%s",t->data);
    }
}

void main()
{
    char *a;
    pos temp,t;
    int j,i;
    puts("Enter the expression :");
    scanf("%s",&a);
    for(i=0;a[i]!='\0';i++)
    {
        if(a[i]=='*' || a[i]=='/' || a[i]=='+' || a[i]=='-')
        {
            temp=newnode(a[i]);
            temp->right=pop();
            temp->left=pop();
            push(temp);
        }
        else
        {
            temp=newnode(a[i]);
            push(temp);
        }
    }
    inorder(temp);
    printf("\n");
    preorder(temp);
    printf("\n");
    postorder(temp);
}

Error : Segmentation Fault

This code is for construction of binary tree traversal and conversion of postfix to infix and prefix. I dont know where am going wrong but it keeps saying the same fault. Can anyone help me with this ?

Answer 1

    scanf("%s",&a); // is the problem. 

scanf accepts pointer and you are passing the address of a pointer. You have to pass only pointer.

    scanf("%s",a); // since a is already pointer, just use a.

And you are not allocating memory. You need to allocate memory to hold the scanned string some thing like this...

    a = (char*)malloc(sizeof(*a) * MAX_SIZE);

Answer 2

You don't use scanf correctly: you give to scanf the address of a pointer to a char, but it is not initialized: it could point to a bad memory address and then you will get the segmentation fault.

You could do something like this:

# define MAX_BUFF_SIZE (64)

void main()
{
 char a[MAX_BUFF_SIZE];
 pos temp,t;
 int j,i;
 puts("Enter the expression :");
 scanf("%s", a);
 /* ... */
 return 0;
}

Or if you prefere dynamic allocation:

# define MAX_BUFF_SIZE (64)

void main()
{
 char *a;
 pos temp,t;
 int j,i;
 a = malloc(sizeof(*a) * MAX_BUFF_SIZE);
 if (a == NULL)
     return -1;
 puts("Enter the expression :");
 scanf("%s", a);
 /* ... */
 free(a);
 return 0;
}

By the way, be aware that using scanf is not safe, read this if you want more informations.

Answer 3

This line

printf("%s", t->data);

tries to print a char (t->data) as a 0-terminated char array (commonly referred to as "string"), which does not work.

To fix this use "%c" instead of "%s".

Answer 4

In order:

• C doesn't have a malloc.h file. The malloc() function and friends are declared in stdlib.h. The malloc.h file, if present, is a system-specific nonstandardness, and should not be used.
• int top=-1;? Odd way to handle indexing. What's wrong with an index grounded at zero?
• You're casting the return value of the malloc() call. In C, this is generally recommended against.
• return is not a function call, it is a statement.
• Your push() function does no bounds checking. If you push more than thirty items, you'll be overwriting memory that doesn't belong to you.
• Your pop() function also does no bounds checking. What happens if you try to pop when there's nothing on the stack?
• You're using the "%s" format specifier to print an element of type char. Undefined Behavior. (All three traversal functions.)
• Your preorder() function is calling inorder(). Oops.
• You declare a as being of type char *, but then you pass it to scanf(). Either declare it as a sufficiently large array, or use malloc() to allocate the storage that you'll be passing to scanf. (Either way, you should be passing a, not &a, to the scanf() function.)
• What happens if my input string starts with */-+?