Thread: Need help with BST Program

Hello All, I'm learning about BST from a book and I'm stuck half way while trying to code a BST. Here's my code:

Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
        int *dataPtr;
        struct node *left;
        struct node *right;
}NODE;
typedef struct
{
        int count;
        NODE *root;
}TREE;
TREE *createTree(void)
{
     TREE *tree;
     tree = (TREE *)malloc(sizeof(TREE));
     if(tree)
     {
             printf("Tree created successfully. . .\n");
             tree->root = NULL;
             tree->count = 0;
     }
     return tree;
}
void addNode(TREE *tree, int *dataInPtr)
{
    NODE *newNode;
    newNode = (NODE *)malloc(sizeof(NODE));
    if(newNode)
    {
        newNode->dataPtr = dataInPtr;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    if(tree->count == 0)
        tree->root = newNode;
    else
        insertNode(tree->root, newNode, dataInPtr);
    (tree->count)++;
}
NODE *insertNode(NODE *root, NODE *newNode, int *dataInPtr)        
{
    if(!root)
        return newNode;
    if(dataInPtr < root->dataPtr)    
    {
        root->left = insertNode(root->left, newNode, dataInPtr);
        return root;
    }
    else
    {
        root->right = insertNode(root->right, newNode, dataInPtr);
        return root;
    }
    return root;
}
void inOrder(NODE *node)
{
     if(node != NULL)
     {
             inOrder(node->left);
             printf("%d\t", node->dataPtr);
             inOrder(node->right);
     }
}
int main(void)
{
    TREE *tree;
    tree = createTree();
    addNode(tree->root, 20);
    inOrder(tree->root);
    getch();
    return 0;
}

I kinda know where the problem lies. In the "else" loop of the addNode() function, I call insertNode() function which is a function with a void return type. But the insertNode() function actually return a NODE type.

I really don't know how to set the left and right nodes. I tried several things but failed. I want to do it on my own. Any help / suggestion would be appreciated.

Thanks in advance.

Code:

typedef struct node
{
        int *dataPtr;
        struct node *left;
        struct node *right;
}NODE;
...
void addNode(TREE *tree, int *dataInPtr)
...
addNode(tree->root, 20);

Why are you passing a value (20) to a function that expects a pointer to int? I think your struct and addNode function are actually incorrect, dataPtr should really just be data, an int:

Code:

typedef struct node
{
        int data;
        struct node *left;
        struct node *right;
}NODE;
...
void addNode(TREE *tree, int dataIn)

Then the comparison Salem mentioned should work.

Updated code would help.

I think your insertNode function is okay (if a bit awkward). The problem seems to lie in the else part of your addNode function. You need to assign the return value of insertNode to tree->root. Also, addNode takes a TREE *, not a NODE *, so you should pass in tree, not tree->root.

Your compiler should be complaining about all these type-mismatch issues. If not, turn up the warning level to the max.

@anduril462: Rightly said mate, there were a few errors which i corrected. And as you said, the problem is definitely in the else part of addNode function, but I don't know how to assign that function. You say that the return value of insertNode to tree->root. But don't you think this is incorrect? Because we assign the tree->root only if the tree->count is 0, that is the tree is just created.

Once tree->count is incremented, we already have a node and the next node should either go to the left or the right of the root which is where am confused.

The updated code is as follows:

Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
        int data;
        struct node *left;
        struct node *right;
}NODE;
typedef struct
{
        int count;
        NODE *root;
}TREE;
TREE *createTree(void)
{
     TREE *tree;
     tree = (TREE *)malloc(sizeof(TREE));
     if(tree)
     {
             printf("Tree created successfully. . .\n");
             tree->root = NULL;
             tree->count = 0;
     }
     return tree;
}
void addNode(TREE *tree, int dataIn)
{
    NODE *newNode;
    newNode = (NODE *)malloc(sizeof(NODE));
    if(newNode)
    {
        newNode->data = dataIn;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    if(tree->count == 0)
        tree->root = newNode;
    else
        insertNode(tree->root, newNode, dataIn);
    (tree->count)++;
}
NODE *insertNode(NODE *root, NODE *newNode, int dataIn)        
{
    if(!root)
        return newNode;
    if(dataIn < root->data)    
    {
        root->left = insertNode(root->left, newNode, dataIn);
        return root;
    }
    else
    {
        root->right = insertNode(root->right, newNode, dataIn);
        return root;
    }
    return root;
}
void inOrder(NODE *node)
{
     if(node != NULL)
     {
             inOrder(node->left);
             printf("%d\t", node->data);
             inOrder(node->right);
     }
}
int main(void)
{
    TREE *tree;
    tree = createTree();
    addNode(tree, 20);
    inOrder(tree->root);
    getch();
    return 0;
}

Hi Salem, I changed the code a bit, I guess it works fine but it doesn't print the output:

The changed code is like this:

Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
        int data;
        struct node *left;
        struct node *right;
}NODE;
typedef struct
{
        int count;
        NODE *root;
}TREE;
TREE *createTree(void)
{
     TREE *tree;
     tree = (TREE *)malloc(sizeof(TREE));
     if(tree)
     {
             printf("Tree created successfully. . .\n");
             tree->root = NULL;
                         tree->count = 0;
     }
     return tree;
}
NODE *addNode(NODE *node, int dataIn)
{
    if(node == NULL)
    {
            NODE *newNode;
            newNode = (NODE *)malloc(sizeof(NODE));
            if(newNode)
            {
                       newNode->data = dataIn;
                       newNode->left = NULL;
                       newNode->right = NULL;
                       node = newNode;
            }
    }
    else
    {
        if(dataIn < node->data)
        {
             node->left = addNode(node->left, dataIn);
             return node;
        }
        else if(dataIn > node->data)
        {
             node->right = addNode(node->right, dataIn);
             return node;
        }
    }
    return node;
}

void inOrder(NODE *node)
{
     if(node != NULL)
     {
             inOrder(node->left);
             printf("%d\t", node->data);
             inOrder(node->right);
     }
}
int main(void)
{
    TREE *tree;
    tree = createTree();
    addNode(tree->root, 20);
    inOrder(tree->root);
    getch();
    return 0;
}

In the inOrder function, the "if" condition doesn't get satisfied, so that means the node is not getting created? Is it?


But I did a bit of debug and I found that the newNode does get created.

Hi Salem, I understand what you're saying. The addNode()function returns a NODE type and am not storing it. But I am not sure what do I assign it to.

If I do it this way

Code:

tree->root = addNode(tree->root, 20);

It would only be applicable for the first node - root, isn't it? Or am I wrong?

Or should I assign it in some other way?

I could only understand a bit of your previous comment. If you can give me some hint, I'll try it out myself.

I've been stuck up with this for the past 5 days.