BST traversal in C

Question

Traversing a tree using C. It will accept a character and prints the post fix/ in fix/ pre fix. The problem is when it prints the output it looks like this

 input
 a
 b
 c
 d
 e
 f
 g
 h
 i   
    IN ORDER:   C abcdefghi
    PRE ORDER:  C  abcdefghi
    POST ORDER:  ihgfedcba C

There are spaces and the character 'C' when I traverse and the pre and post order is wrong. I dont know what is wrong. I am wrong in getting the input here? using scanf to get the address of the char? Here is the whole code

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



typedef struct BST
{
    char data;
    struct BST *lchild, *rchild;
}node;

node *get_node()
{
    node *temp;
    temp=(node *)malloc(sizeof(node));
    temp->lchild=NULL;
    temp->rchild=NULL;
    return temp;
}

void insert(node *root, node *new_node)
{
    if((new_node->data) < (root->data))
    {
            if((root->lchild)==NULL)
            {
                root->lchild=new_node;
            }
            else
            {
                insert(root->lchild,new_node);
            }

    }

    if(new_node->data > root->data)
    {
        if((root->rchild)==NULL)
        {
            root->rchild=new_node;
        }
        else
        {
            insert(root->rchild,new_node);
        }
    }
}

void inorder(node *temp)
{
    if(temp!=NULL)
    {
        inorder(temp->lchild);
        putchar(temp->data);
        inorder(temp->rchild);
    }
}

void preorder(node *temp)
{
    if(temp!=NULL)
    {

            putchar(temp->data);
            preorder(temp->lchild);
            preorder(temp->rchild);

    }
}

void postorder(node *temp)
{
    if(temp!=NULL)
    {
        postorder(temp->lchild);
        postorder(temp->rchild);
        putchar(temp->data);

    }

}

void main()
{
    int i;
    node *new_node, *root, *tmp, *parent;
    node *get_node();
    char c;
    clrscr();

    for(i=0;i<9;i++)
    {
        fflush(stdin);

        new_node=get_node();


        printf("\nenter element: ");
        scanf("%c", &new_node->data);

        if(root==NULL)
        {
            root = new_node;
        }   
        else
        {
            insert(root, new_node);
        }

    }

    printf("\n\nIN ORDER: ");
    inorder(root);
    printf("\nPRE ORDER: ");
    preorder(root);
    printf("\nPOST ORDER: ");
    postorder(root);




    getch();
}

Three unrelated things: First why do you have two nested `if` checks in the `preorder` function that does the same thing? Then *technically* speagin doing `fflush(stdin)` is really *undefined behavior* by the C specification, though some C libraries allow it as an extension (so don't use it in code that's supposed to be portable). Finally, [don't cast the result of `malloc` in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Some programmer dude, Feb 16 '15 at 14:25
As for your problem, can you please show your *input*, exactly *as is*. — Some programmer dude, Feb 16 '15 at 14:26
Lastly, local variables that you don't initialize will have an *indeterminate* value, and using them except for initialization leads to [*undefined behavior*](http://en.wikipedia.org/wiki/Undefined_behavior). This is in regards to your check for `root` being `NULL`. I'll bet anything that the major problem you're having is that. — Some programmer dude, Feb 16 '15 at 14:30
@JamesAdam Yes. I am trying to learn this. Sorry if it makes you sad. — Eyam Saye, Feb 16 '15 at 14:32
How does this have three upvotes? I don't even see a question, just a "Here's the output" and "Here's my code dump" — LittleBobbyTables - Au Revoir, Feb 16 '15 at 14:35
@JoachimPileborg I forgot about that local variables and didnt notice that nested ifs. — Eyam Saye, Feb 16 '15 at 14:41
@LittleBobbyTables: agree. Flagged as Off Topic because of searching debugging help. — eckes, Feb 16 '15 at 15:08

score 0 · Answer 1 · answered Aug 17 '15 at 08:16

There are spaces and the character 'C' when I traverse

This is most probably due to the missing initialization of root, as Joachim Pileborg noticed.

the pre and post order is wrong

They are not; apart from the spaces and the 'C', you have the degenerate (or pathological) tree

for which the output orders are correct.

BST traversal in C

1 Answers1