Root node is not being created in bst

Question

0.00/5 (No votes)

See more:

//The following code does not give any output
//Is there any flaw in its coding.

C#

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


typedef struct Node
{
    int info;
    struct Node* left;
    struct Node* right;
}node;

void insert(node *root,int item)
{
    node *parent,*cur;
    parent=NULL;
    cur=root;
    while(cur!=NULL)
    {
        parent=cur;
        if(item<=cur->info)
        cur=cur->left;
        else
        cur=cur->right;
    }
    if(root==NULL)
    {
        root->info=item;
        root->left=NULL;
        root->right=NULL;
    }
    else
    {
        node *newNode=(int*)malloc(sizeof(node));
        newNode->info=item;
        newNode->left=NULL;
        newNode->right=NULL;
        if(item<parent->info)
        parent->left=newNode;
        else
        parent->right=newNode;
    }
}


int main()
{
    int a[]={5,4,6,9,21,13,45,2};
    int i;
    node *root=(node*)malloc(sizeof(node));
    root=NULL;
    insert(root,4);
    printf("%d",root->info);
    getch();
}

Posted 9-Aug-13 21:02pm

Brady Bar

Add a Solution

Comments

[no name] 10-Aug-13 4:58am

Have you ever run this code in a debugger because it will blow up long before any output. If you don't know what that is then that's something you need to learn. Can you actually compile this without problem?

node *newNode=(int*)malloc(sizeof(node));

2 solutions

Solution 1

No, it is doing exactly what you told it to do.
It's just that what you told it to do is rubbish, that's all! :laugh:

Look at your code.
Why do you have a loop for cur!=NULL at all? you don't do anything with cur after it!
What do you expect this code to do?

C++

if(root==NULL)
{
    root->info=item;
    root->left=NULL;
    root->right=NULL;
}

Because all it will do is crash if root is NULL!
I suspect you need to think about what you are trying to do, and perhaps give it a go manually on pieces of paper first, because this looks very confused!

Posted 9-Aug-13 22:17pm

OriginalGriff

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

nv3 · Accepted Answer · 2013-08-09T23:53:00

As Griff already pointed out there are a couple of things totally wrong in your code, and you can see them by just looking at it. Let's start with your main program:

C++

node *root=(node*)malloc(sizeof(node));
root=NULL;
insert(root,4);

Obviously, you meant to allocate a root node in the first line, but then just for testing purposes reset root to NULL again, in which case the memory you just have allocated would be lost -- a memory leak. Now you have to decide whether you want the user of your insert function to always allocate the root node by himself, or whether you want to start with a root pointer that is NULL. I'd go for the second option. So throw that malloc line out.

So, we have decided that in the very first call the insert function is going to allocate the root node for us. But how can it return that pointer? In the declaration

C++

void insert(node *root,int item)

you specified root as a pointer that is transferred by value. That doesn't give us a chance to return a value back to our caller. To remedy that we have to pass the root pointer via a pointer to a pointer:

C++

void insert (node** ppRoot, int item)

And now we can allocate a root node inside the insert function:

C++

void insert (node** ppRoot, int item)
{
  node* pRoot = *ppRoot;
  if (pRoot == NULL)
  {
    *ppRoot = pRoot = (node*) malloc (sizeof (node));
    pRoot->item = item;
    pRoot->left = NULL;
    pRoot->right = NULL;
  }

In your main function you would now call insert the following way:

C++

root = NULL;
insert (&root, 4);

And there is one other thing that I would change: The parent pointer in your insert function points to the node to which you have to link your newly allocated node. The problem is just that you don't know whether to link it to the left or right pointer of the parent node. You solved that by comparing the item once again to the parent's value. A more elegant way is to use a pointer that point to the location into which the link has to be placed, i.e. (left or

right

).

C++

node** ppLink;
...
while (cur != NULL)
{
  if (item <= cur->info)
    ppLink = &cur->left;
  else
    ppLink = &cur->right;
  cur = *ppLink;
}
...
{
  node* pNewNode = (node*) malloc (sizeof(node));
  *ppLink = pNewNode;
  ...

Got it?

As you see, the concept of pointers to pointers is very powerful. The above explanations were just meant to get you going into the right direction. They don't fix all the problems in your code. In any case: Learn how to use the debugger. That will become your most important tool as a programmer!

Good luck.