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();
}

Answer 1

The issue with these binary search tree (BST) traversals is being affected by degenerate trees arises from the unbalanced structure of the tree

You can either insert values one by one by ensuring the tree is balanced otherwise the tree will go unbalanced in majority of cases

For example : If you insert 10,20,30

The tree will be like

10
20
30

Not like

20 /
10 30

Solution for this is

Using balancing strategies (e.g., AVL, Red-Black) or randomization to avoid degenerate trees.

Answer 2

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

                a
                 \
                  b
                   \
                    c
                     \
                      d
                       \
                        e
                         \
                          f
                           \
                            g
                             \
                              h
                               \
                                i

for which the output orders are correct.