?
Solved

Insertion in Binary Search Tree not working

Posted on 2008-10-25
17
Medium Priority
?
840 Views
Last Modified: 2010-05-18
i am trying to insert n nodes in Binary Search Tree which is initially empty, using function.
i am passing Root and Value to be inserted to function.
it is not working, Root always remains NULL.
Please Check and reply.
given below code is  in C.
/*  InsertBST.C */
#include<stdio.h>
#include<Conio.h>
 
/* Create Structure */
struct node
{
	int info;
	struct node *Left, *Right;
};
struct node *Root=NULL;  /* Make Root Null.*/
 
/* function prototypes : */ 
void Insert(struct node *,int);
void Inorder(struct node *);
 
void main()
{
	int i, n, item;
	clrscr();
	printf("How many nodes :") ;
	scanf("%d", &n);
	for(i=0;i<n;i++)
	{
	printf("\nEnter Item : ");
	scanf("%d", &item);
	Insert(&*Root, item);  /*call function, pass address of Root*/
	printf("\n %p", Root);
	}
getch();
}
 
void Insert(struct node *R, int item)
{
	struct node *NewNode ;
	if(R==NULL)
	{
	/*Create new node, add item to it, make both children NULL */
		NewNode=(struct node*)malloc(sizeof(struct node));
		NewNode->info = item;
		NewNode->Left = NewNode ->Right = NULL ;
		printf("\t%p", NewNode);
		/* Make R point to NewNode */
		R=NewNode ;
	}
	else if(item < R->info)
	{
		Insert(R->Left, item);
	}
	else if(item > R->info)
	{
		Insert(R->Right, item);
	}
	else
	{
		printf("\nError : Duplicate Item, Cant be inserted ");
	}
}
 
void Inorder(struct node *R)
{
	if(R==NULL) return;
	Inorder(R->Left);
	printf("%d", R->info);
	Inorder(R->Right);
}

Open in new window

0
Comment
Question by:sctt_tiger
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 7
17 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 22802540
The Insert function works with a copy of the node pointer. So, whatever change you do to that pointer will be on the copy - ie. the change will not be visible in main.

More specifically, this line :

                R=NewNode ;

modifies the local function copy of the node pointer, not the one in main.


I suggest to design your tree such that an empty tree still has a root struct (not a node with a value - simply a struct that contains a pointer to the root). That way, you can pass that root struct (which contains a null pointer) to the Insert function, which can then modify the node pointer inside that struct to point to the newly created root node.
0
 

Author Comment

by:sctt_tiger
ID: 22803041
Thanks Infinity08.

>> The Insert function works with a copy of the node pointer
But Why ? i am sending address of pointer in line Insert(&*Root) ;

>> I suggest to design your tree such  . . .
How ?
i tried :
instead of :
struct node
{
      int info;
      struct node *Left, *Right;
} *Root=NULL;

i wrote :
struct node
{
      int info;
      struct node *Left, *Right;
} ;
struct node *Root=NULL;

but it didnt work.


please simplify.

Thanks a lot.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22803076
>> But Why ? i am sending address of pointer in line Insert(&*Root) ;

No, you are dereferencing the pointer, and then taking the address. &*Root is the same as just Root.
If you want to pass the address of the pointer, then you need to pass &Root, but then you'd also have to modify the Insert function to accept a struct node** rather than a struct node*.


>> How ?

What I meant is to have another struct called BST (or something similar) :

typedef struct BST {
    struct node *root;
} BST;

This struct represents your BST. When its root member is null, it means the BST is empty. When it's not null, it's pointing to the root node.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:sctt_tiger
ID: 22803220
ok, i will try it by passing &Root.
Thanks.
and
>>
typedef struct BST {
    struct node *root;
} BST;



Mean while, Please also check my question on VB at :
http://www.experts-exchange.com/Programming/Languages/Visual_Basic/VB_Controls/Q_23844294.html

Thansk a lot.
dont want to do this.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22803245
>> ok, i will try it by passing &Root.

It's either one or the other, not both ;) Either the extra struct, or passing &Root. And as I said earlier, I recommend the extra struct.
0
 

Author Comment

by:sctt_tiger
ID: 22807057
>> Mean while, Please also check my question on VB . .
0
 

Author Comment

by:sctt_tiger
ID: 22807293
Hi Infinity !
as per your suggestion, i have changed my program to following.
BUT, now
     1. It has become very complex.
     2. when i tried to run it, it aborted.
Please check, where i am wrong.
Thanks.

#include<stdio.h>
#include<Conio.h>
 
struct node
{
	int info;
	struct node *Left, *Right;
};
 
typedef struct node BST ;
 
BST *Root=NULL;
 
void Insert(BST**,int);
void Inorder(BST **);
 
void main()
{
	int i, n, item;
	clrscr();
	printf("How many nodes :") ;
	scanf("%d", &n);
	for(i=0;i<n;i++)
	{
		printf("\nEnter Item : ");
		scanf("%d", &item);
		Insert(&Root, item);
		printf("\n %p", &Root);
	}
getch();
}
 
void Insert(struct node **R, int item)
{
	struct node *NewNode ;
	if(R==NULL)
	{
		//Create a new node, add item to it, make its both children NULL.
		NewNode=(struct node*)malloc(sizeof(struct node));
		NewNode->info= item;
		NewNode->Left = NewNode ->Right = NULL ;
		printf("\t%p", NewNode);
		//Make R point to NewNode
		R=&NewNode ;
	}
	else if(item < (*R)->info)
	{
		Insert(&(*R)->Left, item);
	}
	else if(item > (*R)->info)
	{
		Insert(&(*R)->Right, item);
	}
	else
	{
		printf("\nError : Duplicate Item, Cant be inserted ");
	}
}
 
void Inorder(BST **R)
{
	if(R==NULL) return;
	Inorder(&(*R)->Left);
	printf("%d", (*R)->info);
	Inorder(&(*R)->Right);
}

Open in new window

0
 

Author Comment

by:sctt_tiger
ID: 22808230
waiting ...
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22808414
>>         if(R==NULL)

You need to check whether *R is NULL. *R is the node pointer, not R.


>>                 R=&NewNode ;

No, you have to assign the pointer :

        *R = NewNode;


One more thing : main HAS to return int, not void. You should fix that.
0
 

Author Comment

by:sctt_tiger
ID: 22809413
ok, i made these changes.
now, Insert function is running.
BUT still Inorder function is not running.
Also, can this statement
            Insert(&(*R)->Left, item);
in Insert function be simplified ?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22810733
>> BUT still Inorder function is not running.

Take a closer look at what it does. And why are you passing a BST** ?

Also : it's your choice not to create a separate BST struct, but it would make things easier.
0
 

Author Comment

by:sctt_tiger
ID: 22820040
actually i am not clear about BST *R1and BST **R2.

though i know R1 is pointer to structure of type BST and R2 is Pointer to such pointer.
but why do i need to pass BST ** to Insert and BST *  to Inorder.
why BST * passed to Insert does not act as pointer ?

Please help to understand this, so that i dont trouble again with question as above.


Thanks.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22820212
>> why BST * passed to Insert does not act as pointer ?

BST* is a pointer. Inside the function you can modify what that pointer points to.

But the problem is that in the Insert function, you want to modify the pointer itself (not only what it points to). So, you need to pass a pointer to the pointer in order to be able to modify the pointer itself.

You wouldn't need to pass a pointer-to-pointer if you would use a separate BST struct as I suggested a few times already.
0
 

Author Comment

by:sctt_tiger
ID: 22852084
hello again.
Please, i have modified code as per my best knowledge and as guided by you.
but still there are some problems,. Inorder() is not working.
program aborts, when i call it from main.
Please Check.

Thanks.
#include<STDIO.h>
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
 
struct node
{
  int info;
  struct node *left,*right;
};
 
struct node *root=NULL;
 
void insert(struct node**, int);
void inorder(struct node*);
void tmp(struct node*) ;
 
 
int main()
{
   clrscr();
   int i, n, item;
   cout<<"\n how many nodes";
   cin>>n;
   for(i=0;i<n;i++)
   {
     cin>>item;
     insert(&root,item);
   }
  // inorder(root);  //Not Working
  tmp(root);   //Giving Wrong OutPut
 
getch();
return 0;
}
 
void tmp(struct node *r)
{
	printf("\n %p  %d  %p", r->left, r->info, r->right);
}
 
void inorder(struct node *r)
{
	if (r==NULL) return;
	inorder(r->left) ;
	printf("%d", r->info);
	inorder(r->right);
}
 
void insert(struct node **r,int val)
{
      struct node *newnode;
      if(*r==NULL)
      {
	       newnode=(struct node*)malloc(sizeof(struct node*));
	       newnode->info=val;
	       newnode->left=NULL ;
	       newnode->right = NULL ;
	       *r = newnode ;
	       printf("\t%p", newnode);
      }
      else if(val < (*r)->info)
	insert(&(*r)->left,val);
      else if(val >  (*r)->info)
	insert(&(*r)->right,val);
      else
	printf("\nDuplicate Error ");
}

Open in new window

0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 400 total points
ID: 22852676
Take a closer look at this line :

>>                newnode=(struct node*)malloc(sizeof(struct node*));

You're not allocating enough memory. It should be :

               newnode=(struct node*)malloc(sizeof(struct node));


btw, you should use the correct standard headers :

#include <stdio.h>                  // <--- lowercase
#include <iostream>                 // <--- iostream.h is deprecated
#include <conio.h>                  // <--- non-standard - keep that in mind
#include <stdlib.h>                 // <--- for malloc etc. (not alloc.h)

Open in new window

0
 

Author Comment

by:sctt_tiger
ID: 22855157
Thanks lot Infinty08 !
oh that was really a stupid misktake.
i will try and revert back.
0
 

Author Comment

by:sctt_tiger
ID: 22856401
yes, it worked.
Thanks a lot.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question