tags:

views:

288

answers:

2

Hi, I'm a Python guy. Learning C language and I've been trying to implement Binary Search Tree in C. I wrote down the code, and I've been trying from few hours but, not able to get the output as expected. Please help!

Please correct me.

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

typedef int ElementType;

typedef struct TreeNode {
  ElementType element;
  struct TreeNode *left, *right;
} TreeNode;

TreeNode *createTree(){
    //Create the root of tree
    TreeNode *tempNode;
    tempNode = malloc(sizeof(TreeNode));
    tempNode->element = 0;
    tempNode->left = NULL;
    tempNode->right = NULL;
    return tempNode;
}

TreeNode *createNode(ElementType X){
    //Create a new leaf node and return the pointer
    TreeNode *tempNode;
    tempNode = malloc(sizeof(TreeNode));
    tempNode->element = X;
    tempNode->left = NULL;
    tempNode->right = NULL;
    return tempNode;
}

TreeNode *insertElement(TreeNode *node, ElementType X){
    //insert element to Tree
    if(node==NULL){
        return createNode(X);
    }
    else{
        if(X < node->element){
            node->left = insertElement(node->left, X);
        }
        else if(X > node->element){
            node->right =  insertElement(node->right, X);
        }
        else if(X == node->element){
            printf("Oops! the element is already present in the tree.");
        }
    }
}

TreeNode *displayTree(TreeNode *node){
    //display the full tree
    if(node==NULL){
        return;
    }
    displayTree(node->left);
    printf("| %d ", node->element); 
    displayTree(node->right);
}

main(){
    //pointer to root of tree #2
    TreeNode *TreePtr;
    TreeNode *TreeRoot;
    TreeNode *TreeChild;

    //Create the root of tree
    TreePtr = createTree();

    TreeRoot = TreePtr;

    TreeRoot->element = 32;
    printf("%d\n",TreeRoot->element);

    insertElement(TreeRoot, 8);
    TreeChild = TreeRoot->left;
    printf("%d\n",TreeChild->element);  

    insertElement(TreeRoot, 2);
    insertElement(TreeRoot, 7);
    insertElement(TreeRoot, 42);
    insertElement(TreeRoot, 28);
    insertElement(TreeRoot, 1);
    insertElement(TreeRoot, 4);
    insertElement(TreeRoot, 5);

// the output is not as expected :(
    displayTree(TreeRoot);
}
+1  A: 

Your insertElement does not always return a value. This is why your recursive calls go wrong. Tell your compiler to warn you about mistakes like that (e.g., on gcc, use -Wall).

displayTree has a similar error, returning nothing when it is specified to return a TreeNode*.

main should also return a value (or you should declare it void).

Thomas
Afaik declaring `main` as returning `void` is deprecated since C99.
Felix Kling
@Thomas Thanks! as per the code suggested by codeaddict, now `insertElement()` function returns a value. It works!
heapzero
@Felix: it's not really deprecated: C99 allows for an implementation-defined entry point, and has the following to say about the return type of `main()`: "If the return type is not compatible with int, the termination status returned to the host environment is unspecified"; for portability reasons, you should avoid implementation-defined and unspecified behaviour as much as possible, ie stick to `int main(void)` and `int main(int argc, char *argv[])`
Christoph
and btw: if you declare `main()` as returning `int`, you may still omit the `return` as reaching the end of `main()` implicitly returns `0`; I myself add the explicit return because I like to test my code in tinyCC, which will return garbage otherwise
Christoph
+2  A: 

The problem is in the insertion. If node is NULL you create a new node and return it. But what if the node is not NULL. You are making correct changes to the right/left subtree but you are not returning anything.

Change

if(X < node->element){
    node->left = insertElement(node->left, X);
}
else if(X > node->element){
    node->right =  insertElement(node->right, X);
}

to:

if(X < node->element){
    node->left = insertElement(node->left, X);
    return node; // add this.
}
else if(X > node->element){
    node->right =  insertElement(node->right, X);
    return node; // add this.
}
codaddict
wow! it works..! Thank you very much codaddict!But, not able to figure out, how exactly it works.Where does the this return value `node` goes? sorry, about the stupid question :)
heapzero
@heapzero: the return value is set as a child node to the parent. If you are not returning anything, then it may pickup the last created node and append it as the child of the parent. Because of this, your newly created nodes have been getting added as the child of the root node only.
Naveen
Thanks @Naveen ! It makes sense now!
heapzero