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.

> if(dataInPtr < root->dataPtr)
You need to store (and compare) values, NOT pointers.

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.

Code:

---

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;
}
...
int main(void)
{
    TREE *tree;
    tree = createTree();
    addNode(tree->root, 20);
    inOrder(tree->root);
    getch();
    return 0;
}

---

Your createTree function can potentially return a NULL pointer, you return "tree" in that function regardless of whether it is NULL or not and then immediately start using it. This can result in problems when you access the returned NULL pointer as you are doing in your calls to addNode and inOrder. You should have a check in main to only proceed if the returned pointer is not NULL.

---

Code:

---

tree = (TREE *)malloc(sizeof(TREE));
...
newNode = (NODE *)malloc(sizeof(NODE));

---

You should avoid casting the return value of your malloc calls where possible. Also, it is preferable from a maintenance standpoint to use the size of the dereferenced variable you are assigning to rather than the size of the type pointed to when passing how many bytes to allocate to malloc. This makes future changes easier since you won't be required to hunt down and fix all those sizeof statements if you change the type of the pointer.

This is a preferable way to write the above:

Code:

---

tree = malloc(sizeof(*tree));
...
newNode = malloc(sizeof(*newNode));

---

Of course if you change the variable name for some reason you'd still have to do some replacement;)

---

Code:

---

#include<conio.h>
...
getch();

---

Unless you have a very good reason for doing so, it's best to avoid non-standard headers and functions. Though it's behavior is different and perhaps undesirable, a more standard approach to this typical "press any key to continue" behavior is to replace getch with getchar and use the return key to end the program.

I removed the pointer to integer from all places and replaced with integer variables. I feel, the problem really lies in the way insertNode() is defined and called. In the else part of addNode() function, insertNode() is called as a function with void return type.

However in reality, insertNode() returns a NODE type. I know this is wrong, but am not able to figure out a way to do this.

insertNode returns a pointer to a node. Not a node!

If I were you I would post my updated code ;)

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

---

Look at line 40
insertNode(tree->root, newNode, dataIn);

Look at line 43
NODE *insertNode(NODE *root, NODE *newNode, int dataIn)

Now back to line 40
insertNode(tree->root, newNode, dataIn);

What happens to the red bit?
You're returning a result, but ignoring it.

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.

So back to line 70, where is THAT result being stored?

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?

Did you try the modification?
Did it work?

> It would only be applicable for the first node - root, isn't it? Or am I wrong?
Yes, it only applies to the first assignment.

But then again,
node->left = addNode(node->left, dataIn);
will only ever assign a different value the FIRST time each node gets added into the tree.
Thereafter, it will always end up assigning the same value.

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.

Try this as your main

Code:

---

int main(void)
{
    TREE *tree;
    tree = createTree();
    int i;
    for ( i = 0 ; i < 10 ; i++ ) {
      printf("Root was %p;", (void*)tree->root);
      tree->root = addNode(tree->root, rand() % 100);
      printf("Root is %p\n", (void*)tree->root);
    }
    inOrder(tree->root);
//    getch();
    return 0;
}

---

I get

Code:

---

$ ./a.out
Tree created successfully. . .
Root was (nil);Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
Root was 0x1809030;Root is 0x1809030
15        21        35        49        77        83        86        92        93        $

---

Thanks Salem, its working. I'm making some modifications in the program to make it work my way. If I have any issues, I'll get back.

Thanks again.

Hello, I've completed my program but there seems to be some minor issue which I've been trying hard to figure out. Here's the code:

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)
    {
            tree->count = 0;
            tree->root = NULL;
    }
    return tree;
   
}
NODE *addNode(TREE *tree, 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;
                        (tree->count)++;
            }
    }
    else
    {
        if(dataIn < node->data)
        {
                  node->left = addNode(tree, node->left, dataIn);
                  return node;
        }
        else
        {
            node->right = addNode(tree, 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);
    }
}
void preOrder(NODE *node)
{
    if(node != NULL)
    {
            printf("%d\t", node->data);
            preOrder(node->left);
            preOrder(node->right);
    }
}
void postOrder(NODE *node)
{
    if(node != NULL)
    {
            postOrder(node->left);
            postOrder(node->right);
            printf("%d\t", node->data);
           
    }
}
int findNode(NODE *node, int findData)
{
    if(node == NULL)
            return 0;
    if(findData == node->data)
                return 1;
    else if(findData < node->data)
        findNode(node->left, findData);
    else
        findNode(node->right, findData);
}
NODE *findNewRoot(TREE *tree, NODE *node, int delData, int *success)
{
    NODE *dltPtr;
    NODE *exchPtr;
    NODE *newRoot;
    int temp;
    if(!node)
    {
              *success = 0;
              return NULL;
    }
    if(delData < node->data)
                node->left = findNewRoot(tree, node->left, delData, success);
    else if(delData > node->data)
                    node->right = findNewRoot(tree, node->right, delData, success);
    else
    {
        dltPtr = node;
        if(!node->left)
        {
                        newRoot = node->right;
                        free(dltPtr);
                        *success = 1;
                        return newRoot;
        }
        else if(!node->right)
        {
              newRoot = node->left;
              free(dltPtr);
              *success = 1;
              return newRoot;
        }
        else
        {
            exchPtr = node->left;
            while(exchPtr)
                          exchPtr = exchPtr->right;
            temp = node->data;
            node->data = exchPtr->data;
            exchPtr->data = temp;
            node->left = findNewRoot(tree, node->left, exchPtr->data, success);
        }
    }
    return node;
}
                         
int main(void)
{
    TREE *tree;
    tree = createTree();
    int value;
    while(1)
    {
            printf("\n1. Insert");
            printf("\n2. Delete");
            printf("\n3. Find");
            printf("\n4. InOrder");
            printf("\n5. PreOrder");
            printf("\n6. PostOrder");
            printf("\nChoice: ");
            scanf("%d", &value);
            if(value == 1)
            {
                    int data;
                    printf("\nEnter data to be inserted: ");
                    scanf("%d", &data);
                    tree->root = addNode(tree, tree->root, data);
            }
            else if(value == 2)
            {
                int delData;
                printf("\nEnter node to be deleted: ");
                scanf("%d", &delData);
                if(findNode(tree->root, delData) == 1)
                {
                              int success;
                              NODE *newRoot;
                              newRoot = findNewRoot(tree, tree->root, delData, &success);
                              if(success == 1)
                              {
                                        tree->root = newRoot;
                                        (tree->count)--;
                                        if(tree->count == 0)
                                                        tree->root = NULL;
                                        printf("\n\nNode deleted successfully. . .");
                              }
                              else
                              {
                                  printf("\n\nNode not deleted. . .");
                              }
                }
                else
                {
                    printf("\n\nNode %d not found. . .", delData);
                }
            }
            else if(value == 3)
            {
                int findData;
                printf("\nEnter value to be found: ");
                scanf("%d", &findData);
                if(findNode(tree->root, findData) == 1)
                {
                              printf("\n\nNode %d found\n\n", findData);
                }
                else
                {
                              printf("\n\nNode %d not found\n\n", findData);
                }
            }
          else if(value == 4)
          {
              printf("\n\n");
              printf("---------------InOrder Traversal--------------\n\n");
              inOrder(tree->root);
              printf("\n\n");
              printf("-----------------------------------------------\n");
          }
          else if(value == 5)
          {
              printf("\n\n");
              printf("---------------PreOrder Traversal--------------\n\n");
              preOrder(tree->root);
              printf("\n\n");
              printf("-----------------------------------------------\n");
          }
          else if(value == 6)
          {
              printf("\n\n");
              printf("---------------PostOrder Traversal--------------\n\n");
              postOrder(tree->root);
              printf("\n\n");
              printf("-----------------------------------------------\n");
          }
          else
              exit(1);
    }
    getch();
    return 0;
}

---

After using option 1 to insert three nodes - "20", "10" and "30" when I try to find "10" using option 3, it says "Node 10 not found" even though the node is present. Even the print options show that the node is present.

I did a little debug and figured out that findNode() function does return a 1, but the if condition doesn't catch it. What could be the issue?

Your recursive calls of findnode don't return anything.

Quote:

---

Originally Posted by Salem

Your recursive calls of findnode don't return anything.

---

Thanks Salem, for your reply. I couldn't find out how to do it the recursive way, hence I tried the iteration method and now it seems to work fine. Here's the updated code of findNode().

Code:

---

int findNode(NODE *node, int findData)
{
    while(node != NULL)
    {
              if(findData == node->data)
                          return 1;
              else if(findData < node->data)
                                node = node->left;
              else if(findData > node->data)
                                node = node->right;
    }
    return 0;
                               
}

---

We did all this 2 weeks ago with insertNode, and you were either not returning a result, or just ignoring the result.

Oh well,

Code:

---

int findNode(NODE *node, int findData)
{
    if(node == NULL)
            return 0;
    if(findData == node->data)
                return 1;
    else if(findData < node->data)
        return findNode(node->left, findData);
    else
        return findNode(node->right, findData);
}

---

Were you by any chance getting any warnings from your compiler.
Say for example "not all return paths return a result"?

Salem: Thanks for the suggestion on the recursive code. Honestly am a bit weak with recursion, hence I chose the iterative method.

The code that I posted earlier, did not give me any warnings like the one you mentioned.