Binary Search Tree in C

Question

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

what exactly meant by "not able to get the output as expected" ? — Naveen
– Naveen, Commented Mar 24, 2010 at 10:44
@Naveen I get | 5 | 32 | 42 when calling displayTree() function. I expect it to print remaining Elements also. — heapzero
– heapzero, Commented Mar 24, 2010 at 10:47
@Naveen Hi, I've tried copy-pasting the code from above, and the 'createTree' function would not compile. I then added the (TreeNode*) cast before malloc and it worked. I'm wondering- does this have something to do with the fact that I'm using an old c89 compiler? — programstinator
– programstinator, Commented Mar 28, 2013 at 22:40

codaddict · Accepted Answer · 2010-03-24 10:53:02Z

5

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.
}

answered Mar 24, 2010 at 10:53

codaddict

457k83 gold badges501 silver badges537 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

heapzero Over a year ago

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 :)

Naveen Over a year ago

@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.

programstinator Over a year ago

@codaddict Shouldn't the first return statement in the 'insertElement' function be return node = createNode(X) ?

Thomas · Accepted Answer · 2010-03-24 10:49:45Z

2

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).

answered Mar 24, 2010 at 10:49

Thomas

183k57 gold badges383 silver badges510 bronze badges

4 Comments

Felix Kling Over a year ago

Afaik declaring main as returning void is deprecated since C99.

heapzero Over a year ago

@Thomas Thanks! as per the code suggested by codeaddict, now insertElement() function returns a value. It works!

Christoph Over a year ago

@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 Over a year ago

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

Collectives™ on Stack Overflow

Binary Search Tree in C

2 Answers 2

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related