A binary search tree code

[swissknife007]

#include<stdio.h>
	#include<conio.h>
	#include<stdlib.h>
	struct node
		{struct node * left;
				struct node * right;
				int info;
		};
	typedef struct node node;
	node * root=NULL,*loc,*par,*save,*child;
	int item;
	void pre(node *);
	void in(node *);
	void post(node *);
	void find()
	   { 
                  node * ptr; 
		  loc=root;
		  par=NULL;
		  if(root==NULL)
				{ 
                                  loc=NULL;
				  par=NULL;
				  return;
				}              
		  if(root->info==item)
				 {
                                  loc=root;
				  par=NULL;
				}    
		 if(item<root->info)
				{
                                  ptr=root->left;

                                 save=root;
                                }
		else
				{
                                  ptr=root->right;
                                  save=root;
                                }
		while(ptr!=NULL)
			{if(item==ptr->info)
				{
                                   loc=ptr;
                                   ptr=save;return;
                                }
				if(item<root->info)
				{save=ptr;ptr=ptr->left;}
				else
				{save=ptr;ptr=ptr->right;
				}
				}
				loc=NULL;par=save;
				}
	void create()
	    {
              node * new1;
	      printf("enter item");
	      scanf("%d",&item);
	      find();
	      if(loc!=NULL)
	               printf("node already present\n");
	      else
	        {
                   new1=(node*)malloc(sizeof(node*));
		   new1->info=item; 
                   new1->left=NULL;
	             new1->right=NULL;                             
		     if(par==NULL)
				     {  root=new1;
				     }
		     else
			{if(item<par->info)
			      par->left=new1;
			else
			      par->right=new1;
			 }
		}
				     
	}
	void del1()
				
             {
			 if(loc->left==NULL&&loc->right==NULL)	 
				 {child=NULL;}
			 else if(loc->left!=NULL)
				 child=loc->left;
			 else
				 child=loc->right;
			 if(par!=NULL)
				 {
                                  if(loc==par->left)
				     par->left=child;
				  else
				     par->right=child;
				 } 
			 else root=child;

	 }
				
	void del()
		{
			printf("enter item to be deleted");
			scanf("%d",&item);
			find();
			if(loc==NULL)
			      { 
                                printf("not present ");return;}
				if(loc->right!=NULL&&loc->left!=NULL)
				  return;
			        else
				{
                                 del1();
                                 printf("here in del1");
                                }
        }
				
	void pre(node * temp)
		{
			 if(temp==NULL)
				  return;
			 printf("%d\t",temp->info);
			 pre(temp->left);
			 pre(temp->right);
				
		}

	void in(node * temp)
		{
		    if(temp==NULL)
			return;
		    in(temp->left);
		    printf("%d\t",temp->info);
		    in(temp->right);
		}

	void post(node * temp)
		{
                      if(temp==NULL)
			return;
		      post(temp->left);
		      post(temp->right);  
		      printf("%d\t",temp->info);
				  
				}
	int main()
		{int ch=1;
		 do{
		printf("\nMENU......\n");
		printf("1)Add nodes\n");
		printf("2)Preorder\n");
		printf("3)Inorder\n");
		printf("4)Postorder\n");
		printf("5)Delete\n");
		printf("enter choice");
		scanf("%d",&ch);
		switch(ch)
		               {
                                case 1:create();break;
				case 2:pre(root);break;
				case 3:in(root);break;
				case 4:post(root);break;
				case 5:del();break;
				default:return 0;
                               }
		printf("do you want to continue1/0\n");
		scanf("%d",&ch);
			
		}while(ch!=0); 
		getch();    
		return 0;
		}

I am running this program in Bloodshed Dev C++.
When I run it in normal execution,all the entries of the tree become 2 .
However,in Debug Mode insertion and traversal work fine.
I am not able to understand this........
del1() deletes a node if present and has only 0 or 1 children.
But del1() is deleting the whole tree in my case....
Any help will be appreciated.

PS:I am a Beginner

[swissknife007]

No help yet!!!
Please help me Princess of Coding.................

[Narue]

Your code is awful and I'm not terribly interested in making it better. Please read this tutorial and try to match your algorithms to the sample code.

[swissknife007]

Your code is awful and I'm not terribly interested in making it better. Please read this tutorial and try to match your algorithms to the sample code.

You mean to say that you accept defeat in front of awfulness of my code
My code may be terrible,but can anyone tell me what is wrong in my code ?

Thanks for the link...I checked the algorithm of my code.I could not find any mistake.

[Narue]

My code may be terrible,but can anyone tell me what is wrong in my code ?

That's a hole with no bottom. How about offering some reproduction steps for troubleshooting the issue? Tell us how to create a tree and then break it with this program exactly the way you are.

[swissknife007]

That's a hole with no bottom. How about offering some reproduction steps for troubleshooting the issue? Tell us how to create a tree and then break it with this program exactly the way you are.

Narue
I write the algorithm first on a sheet of paper then I write the code
there 's hardly any question of the logic of the program being wrong
because I have even matched the algorithms 3-4 times.The issue must be in conversion of algorithm to code.
That is what I am trying to sort out.
Help...
Also pre() ,post(),in() are pretty much redundant.....
All the problems lie with find(),create() and del()

[Narue]

Give me reproduction steps, please. I'm not going to randomly create trees looking for whatever degenerate case you've managed to hit. Since this program is user-interactive, I need to know what options and values you selected to produce the error.

Alternatively, you can remove that whole user input loop and replace it with a driver that breaks consistently.

[swissknife007]

Give me reproduction steps, please. I'm not going to randomly create trees looking for whatever degenerate case you've managed to hit. Since this program is user-interactive, I need to know what options and values you selected to produce the error.

Alternatively, you can remove that whole user input loop and replace it with a driver that breaks consistently.

No ma'am ,the issue is not user input specific.
After taking input 5-6 or 6 times for insertion,the program terminates without any error.
Also,as I take input,the entries in the tree start becoming 2 one-by one.
Eg
Enter input
45
inorder 45
Enter input
78
inorder 2 78

like this.
The delete function doesn't work altogether.Sometimes it deletes the whole tree ,or else shows node not present.Despite all attempts at debugging,there is no result.
You know I made almost identical program in c++ with a tree class,and it works perfectly.
There might be an issue with global and local variables.

[Narue]

I got this far before discovering your problem:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node {
    struct node * left;
    struct node * right;
    int info;
};
typedef struct node node;

node * root=NULL;
int item;

node *find(node **par)
{
    node *loc = root;
    
    *par = NULL;
    
    while (loc != NULL && loc->info != item) {
        *par = loc;
        loc = item < loc->info ? loc->left : loc->right;
    }
    
    return loc;
}

void create()
{
    node *new1, *par;
    node *loc = find(&par);
    
    if(loc!=NULL)
        printf("node already present\n");
    else {
        new1=(node*)malloc(sizeof(node));
        new1->info=item;
        new1->left=NULL;
        new1->right=NULL;
        if(par==NULL) {
            root=new1;
        }
        else {
            if(item<par->info)
                par->left=new1;
            else
                par->right=new1;
        }
    }

}

void structure_r(node *root, int depth)
{
    if (root == NULL) {
        for (int i = 0; i < depth; i++)
            putchar('\t');

        puts("~");
    }
    else {
        structure_r(root->right, depth + 1);

        for (int i = 0; i < depth; i++)
            putchar('\t');

        printf("%d\n", root->info);

        structure_r(root->left, depth + 1);
    }
}

void structure(node *root)
{
    structure_r(root, 0);
}

int main()
{
    int a[] = {3, 5, 2, 4, 1, 6};

    for (int i = 0; i < sizeof a / sizeof *a; i++) {
        item = a[i];
        create();
        structure(root);
        //getchar();
        puts("=========================================");
    }
}

The error is on this line in create():

new1=(node*)malloc(sizeof(node*));

You're allocating memory for a pointer rather than a whole node. The line should be:

new1=(node*)malloc(sizeof(node));

Give that a try and see if it works out for you.

[swissknife007]

I got this far before discovering your problem:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node {
    struct node * left;
    struct node * right;
    int info;
};
typedef struct node node;

node * root=NULL;
int item;

node *find(node **par)
{
    node *loc = root;
    
    *par = NULL;
    
    while (loc != NULL && loc->info != item) {
        *par = loc;
        loc = item < loc->info ? loc->left : loc->right;
    }
    
    return loc;
}

void create()
{
    node *new1, *par;
    node *loc = find(&par);
    
    if(loc!=NULL)
        printf("node already present\n");
    else {
        new1=(node*)malloc(sizeof(node));
        new1->info=item;
        new1->left=NULL;
        new1->right=NULL;
        if(par==NULL) {
            root=new1;
        }
        else {
            if(item<par->info)
                par->left=new1;
            else
                par->right=new1;
        }
    }

}

void structure_r(node *root, int depth)
{
    if (root == NULL) {
        for (int i = 0; i < depth; i++)
            putchar('\t');

        puts("~");
    }
    else {
        structure_r(root->right, depth + 1);

        for (int i = 0; i < depth; i++)
            putchar('\t');

        printf("%d\n", root->info);

        structure_r(root->left, depth + 1);
    }
}

void structure(node *root)
{
    structure_r(root, 0);
}

int main()
{
    int a[] = {3, 5, 2, 4, 1, 6};

    for (int i = 0; i < sizeof a / sizeof *a; i++) {
        item = a[i];
        create();
        structure(root);
        //getchar();
        puts("=========================================");
    }
}

The error is on this line in create():

new1=(node*)malloc(sizeof(node*));

You're allocating memory for a pointer rather than a whole node. The line should be:

new1=(node*)malloc(sizeof(node));

Give that a try and see if it works out for you.

Thanks a ton for that.
What errors I can make......
The problem with create() is gone
But the delete function is still not working properly

[Narue]

But the delete function is still not working properly

Once again you fail to provide enough information.

[swissknife007]

Once again you fail to provide enough information.

Suppose I want to delete the root,it deletes the whole tree.
Basically my delete function is deleting every node before it in the inorder travsersal of the tree

Please help urgently.

[swissknife007]

Suppose I want to delete the root,it deletes the whole tree.
Basically my delete function is deleting every node above the node to be deleted in hierarchy(level)

Please help urgently.

This is true for other nodes also.
In some cases the program terminated unexpectedly.