Awkward Error in C++ (Binary Tree)

[Dragonizer]

I'm using a binary tree, and each time I insert into it, it says that there is nothing there. here is my code:

#ifndef BST_H
#define BST_H

#include <stdlib.h>

class Node{
	int data;
public:
	Node(int d){data = d; left = NULL; right = NULL;}
	~Node(){}
	Node * left;
	Node * right;
	int getData() {return data;}
};

class BST{
private:
	Node * top;
	void cleanup(Node * h);
public:
	BST(){top=NULL;}
	~BST(){cleanup(top);}
	int Insert(const int& data);
	int iinsert(Node * t, const int& data);
};

void BST::cleanup(Node * t)
{
	if(t != NULL)
	{
		cleanup(t->left);
		cleanup(t->right);
		delete t;
	}
}

int BST::Insert(const int& data)
{
	return iinsert(top, data);
}

int BST::iinsert(Node * t, const int& data)
{
	if(t == NULL)
	{
		t = new Node(data);
		return 1;
	}
	else if(data == t->getData())
	{
		return 0;
	}
	else if(data < t->getData())
	{
		return iinsert(t->right, data);
	}
	else if(data > t->getData())
	{
		return iinsert(t->right, data);
	}
}

#endif

this is only the insert method. Does this look right, or did I do something wrong?

[Banfa]

surely this

	else if(data > t->getData())
	{
		return iinsert(t->right, data);
	}

should be

	else if(data > t->getData())
	{
		return iinsert(t->[b]left[/b], data);
	}

i.e. at the moment you use the right pointer twice and the left pointer never.

[Dragonizer]

that's correct, I didn't even notice that. But each time I do an Insert, the top remains null afterwards.

[Dragonizer]

I've modified this code to include a different version of insert:

#ifndef BST1_H
#define BST1_H

#include <stdlib.h>

class Node{
	int data;
public:
	Node(int d){data = d; left = NULL; right = NULL;}
	~Node(){}
	Node * left;
	Node * right;
	int getData() {return data;}
};

class BST{
private:
	Node * top;
	void cleanup(Node * h);
public:
	BST(){top=NULL;}
	~BST(){cleanup(top);}
	int Insert(const int& data);
	int Insert_2(const int& data);
	int iinsert(Node * t, const int& data);
};

int BST::Insert_2(const int& data)
{
	if(top == NULL)
	{
		top = new Node(data);
	}
	else{
		Node * ptr = top;
		while(ptr != NULL)
		{
			if(data == ptr->getData())
			{
				return 0;
			}
			else if(data < ptr->getData())
			{
				ptr = ptr->left;
			}
			else
			{
				ptr = ptr->right;
			}
		}
		ptr = new Node(data);
	}
}

void BST::cleanup(Node * t)
{
	if(t != NULL)
	{
		cleanup(t->left);
		cleanup(t->right);
		delete t;
	}
}

int BST::Insert(const int& data)
{
	return iinsert(top, data);
}

int BST::iinsert(Node * t, const int& data)
{
	if(t == NULL)
	{
		t = new Node(data);
		return 1;
	}
	else if(data == t->getData())
	{
		return 0;
	}
	else if(data < t->getData())
	{
		return iinsert(t->left, data);
	}
	else
	{
		return iinsert(t->right, data);
	}
}

#endif

But it still causes the same problem, so the code:

#include "bst1.h"

int main()
{
	BST t1;
	BST t2;
	t1.Insert(5);
	t1.Insert(11);
	t1.Insert(1);

	t2.Insert_2(5);
	t2.Insert_2(11);
	t2.Insert_2(1);
	return 0;
}

just before the return, the debugger says:
t1->top = NULL
t1->top->left = NULL
t1->top->right = NULL
t2->top = (5)
t2->top->left = NULL
t2->top->right = NULL

does anyone have any idea why this is the case? Maybe I have some pointer issues? But I don't see any, and most sites says to do the insert recursively.

[Banfa]

Because this line

ptr = new Node(data);

in insert_2

assigns data to a local variable, ptr, but not to any of the pointers in the Node data structures hanging off top.

Actually insert_2 is a classic location for a pointer to pointer

[code]
Node **ptrptr;

ptrptr = ⊤

while(*ptrptr != NULL)
{
if (data < (*ptrptr)->data)
{
ptrptr = &(*ptrptr)->left;
}
else if (data > (*ptrptr)->data)
{
ptrptr = &(*ptrptr)->left;
}
else
{
return 0;
}
}

(*ptrptr) = new Node;

if (*ptrptr != NULL)
{
(*ptrptr)->data = data;
}
[code]

By having a pointer to pointer we search for and find the location that we wish to allocate a new node to. Byt only having a pointer you search for and find the value of the pointer where you wish to allocate a new node (which is guaranteed to be NULL).

Assuming no dupicate is found then your loop in insert_2 is equivilent to the statement

ptr = NULL;

[Dragonizer]

thanks a lot