Recursive call going wrong somewhere

[vexiked]

Hey all... I have been pounding my head for the last 3 hours trying to figure out where I am going wrong. Any help would be appreciated.

#include <iostream>
#include <time.h>

using namespace std;

struct BinaryNode
{
	int element;
	BinaryNode *left;
	BinaryNode *right;
};


void Insert(int,BinaryNode*);
int AvgDepth(BinaryNode*);


int main()
{
 int n;
 int j = 1;
 srand (time(NULL) );

 cout << "Please enter n to test: ";
 cin >> n;

 while (j <= n*2)
 {
  BinaryNode *tree = NULL;

 for (int i = 0; i < n; i++)
 {
	Insert(rand()%100, tree);
 }
 cout << endl << "The average depth of tree " << j << " is: " << AvgDepth(tree);
 j++;
 }
 
 return 0;

}

void Insert(int x,BinaryNode* tree)
{        
	if (tree == NULL)        
	{             
	tree = new BinaryNode;               
	tree->right = NULL;                
	tree->left = NULL;                
	tree->element = x;        
	}
else if (x < tree->element)              
	Insert(x,tree->left);     
else               
	Insert(x,tree->right);
}

int AvgDepth(BinaryNode *node)
{ 
  if (node==NULL) 
  { 
    return 0; 
  } 
  else { 
    int n_leftdepth = AvgDepth(node->left); 
    int n_rightdepth = AvgDepth(node->right); 
    return (n_leftdepth+n_rightdepth/2); 
  } 
}

[hamsterman]

in you "insert" function you take BinaryNode* as an argument. this is a copy od BinaryNode* from your main function. when you allocate new BinaryNode you assign its address to the copy, not the "tree" from int main. to make this work try BinaryNode** or BinaryNode*& as argument instead.

[vexiked]

Ok I have done that but it seems that whenever a child is to be added it fails.

#include <iostream>
#include <time.h>

using namespace std;

struct BinaryNode
{
	int element;
	BinaryNode *left;
	BinaryNode *right;
};


void Insert(int,BinaryNode* &);
int AvgDepth(BinaryNode*);


int main()
{
 int n;
 int j = 1;
 srand (time(NULL) );

 cout << "Please enter n to test: ";
 cin >> n;

 while (j <= n*2)
 {
  BinaryNode *tree = NULL;

 for (int i = 0; i < n; i++)
 {  
	Insert(rand()%100, tree);
 }
 cout << endl << "The average depth of tree " << j << " is: " << AvgDepth(tree);
 j++;
 }
 
 return 0;

}

void Insert(int x,BinaryNode* &root)
{        
	if (root == NULL)        
	{             
	root = new BinaryNode;               
	root->right = NULL;                
	root->left = NULL;                
	root->element = x;        
	}
else if (x < root->element)              
	Insert(x,root->left);     
else if (x < root->element)               
	Insert(x,root->right);
   
}

int AvgDepth(BinaryNode *node)
{ 
  if (node==NULL) 
  { 
    return 0; 
  } 
  else { 
    int n_leftdepth = AvgDepth(node->left); 
    int n_rightdepth = AvgDepth(node->right); 
    return (n_leftdepth+n_rightdepth/2); 
  } 
} 

[guestgulkan]

Well you corrected one problem but created another.
the following function is incorrect:

void Insert(int x,BinaryNode* &root)
{        
	if (root == NULL)        
	{             
	root = new BinaryNode;               
	root->right = NULL;                
	root->left = NULL;                
	root->element = x;        
	}
else if (x < root->element)              
	Insert(x,root->left);     
else if (x < root->element)      //here is a problem         
	Insert(x,root->right);
   
}