Unable to create Binary Search Tree

Question

Well,I'm trying to create an unbalanced Binary Search Tree from a given input as a sequence of (unsorted) integers.
My approach has been to recursively find the right place for each individual node and then allocate memory for it and define the data for it.
But I'm unable to debug the program effectively as despite having scrutinised it properly,I can't seem to identify the problem. For an input as follows:
So for Input:

11
15 6 4 8 5 3 1 10 13 2 11

The Expected output should have been the post-order and in-order traversals,but strangely nothing is getting printed(Except for the newline I've given in between).

Update:
1.[20 March 2015]-Taking due consideration of the warning,removed the malloc typecast.
2. [21 March 2015] Made certain changes, although now, the code is only giving the following output:

11 13
11 13 

Here's the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arrmax 100
/***Pointer-based BST implementation, developed by Abhineet Saxena***/

/***The data-type declaration***/
typedef struct node{
int data;
struct node* parent;
struct node* leftChild;
struct node* rightChild;
}Node;

typedef struct tree
{
    Node* root;
    int size;
}BSTree;

/***Method prototypes***/
/*Method to create a tree*/
Node* createTree(int[],int,int);

//Changed from void to Node*: void createNode(Node*,int);
Node* createNode(Node*,int);
void inOrder(Node* root);
void postOrder(Node *root);

int main(void) {

    BSTree* bs_tree;
    //Incorrect here: bs_tree=(BSTree*)malloc(sizeof(BSTree));
    bs_tree=malloc(sizeof(BSTree));
    bs_tree->root=NULL;
    bs_tree->size=0;
    /****Taking the input****/
    int num_elem,iterv;
    scanf("%d\n",&num_elem);
    //Incorrect here: int *arr=(int*)malloc(sizeof(int)*(num_elem));
    int *arr=malloc(sizeof(int)*(num_elem));
    for(iterv=0;iterv<num_elem;iterv++)
    {
        scanf("%d",&arr[iterv]);
    }
    bs_tree->root=createTree(arr,0,num_elem-1);
    postOrder(bs_tree->root);

    printf("\n");
    inOrder(bs_tree->root);

    return 0;
}
Node* createTree(int marr[],int left,int right)
{
    int iterv;
    Node* root;
    root=NULL;
    for(iterv=left;iterv<=right;iterv++)
    {

        //Made changes here: Old:-createNode(root,marr[iterv]);
         root=createNode(root,marr[iterv]);

    }
    return root;
}
Node* createNode(Node* root,int key)
{
    if(root==NULL)
    {
        root=malloc(sizeof(Node));
        //printf("Used malloc here for key: %d\n",key);
        root->data=key;
        root->leftChild=NULL;
        root->rightChild=NULL;
        root->parent=NULL;
        //Changed here: [old]return;
        return root; 

    }
    else
    {
        if(key<root->data)
                {

                        //Added code here[Old: createNode(root->leftChild,key);]
                        if(root->leftChild!=NULL)
                            createNode(root->leftChild,key);
                       else
                       {
                           root->leftChild=createNode(root->leftChild,key);
                           return root;
                       }
                }
        else
                //Added Code here: [old codeline:-] createNode(root->rightChild,key);
                 {
                     if(root->rightChild!=NULL)
                          createNode(root->rightChild,key);
                    else
                     {
                         root->rightChild=createNode(root->rightChild,key);
                         return root;
                     }
                 }                  
    }
}

void inOrder(Node* bst_tree)
{
    if(bst_tree!=NULL)
    {
        inOrder(bst_tree->leftChild);
        printf("%d ",bst_tree->data);
        inOrder(bst_tree->rightChild);
    }
    else
        return;
}
void postOrder(Node* bst_tree)
{
    if(bst_tree!=NULL)
    {
        postOrder(bst_tree->leftChild);
        postOrder(bst_tree->rightChild);
        printf("%d ",bst_tree->data);
    }
    else
        return;
}

Answer 1

I think, the problem is in void createNode(Node* root,int key) function. The variable Node* root is local to the function. So the changes won't be reflected outside createNode().

Just FYI, C uses pass-by-value to pass function parameters.

So, either you've to

1. return the newly allocated root from createNode() and collect it in caller. You need to change the return type of createNode() function to Node * (or void *, atleast) also.

or

2. Use a pointer to Node * as argument in createNode()

Important Note: Always free() the allocated memory after you're done using them. Otherwise, it'll lead to memory leak.

Answer 2

Your createNode() function allocates memory for a node and fills it with data but I can't see it links the new node to the rest of a data structure. All your leftChild and rightChild pointers as well as the tree root remain NULL.

So you have plenty of nodes somewhere on the heap but your tree is empty...

When you do in main()

bs_tree->root = createTree(arr,0,num_elem-1);

you should also do in createTree()

root = createNode(root,marr[iterv]);

and in createNode()

root->leftChild = createNode(root->leftChild,key);
root->rightChild = createNode(root->rightChild,key);

and of course return root; from all those functions.

EDIT

Possible implementation:

Node* insertNode(Node* root, int value)
{
    if(root == NULL)
    {
        root = malloc(sizeof(Node));
        root->data = val;
        root->leftChild = NULL;
        root->rightChild = NULL;
    }
    else
        if(val < root->data)
            root->leftChild = insertNode(root->leftChild, val);
        else
            root->rightChild = insertNode(root->rightChild, val);

    return root;
}

Answer 3

This part is not correct:

void createNode(Node* root,int key)
{
     ...
     root=(Node*)malloc(sizeof(Node));
     ...
}

root is your argument, and changing its value (you store another address in it) is rarely a good idea. You must either use a pointer to that pointer:

void createNode(Node** root,int key)
{
     ...
     *root = malloc(sizeof(Node));
     ...
}

or return the new value at the end:

Node* createNode(Node* root,int key)
{
     ...
     root = malloc(sizeof(Node));
     ...

     return root;
}