Recursion Stack Overflow...

[Lv0f92yv]

This code:

void BST::print( Node* n )
{
	//print the tree here
	if ( n == NULL )
		return; //base case
	//in order print
	print(n->left);
	n->_hs->print();
	print(n->right);
}

causes a stack overflow error. It was working fine when my Nodes contained a primitive type. It's 3 AM and if I'm missing something painfully obvious here slap me.

[Albatross]

/slap Desh
We... generally hate recursion here, and this would be why: it's easy to create stack overflows with it. Even I admit that it's a fairly dangerous feature of C++, and use it sparingly. Why not use an infinite while loop?

Oh, and might I ask what Node is defined to be?

-Albatross

[Lv0f92yv]

Yea. Figured.

After stepping through a few more times, it appears that n->left points conveniently to n. (Memory addresses are the same).

I presume this problem to be the way in which I am adding the nodes (also recursively). I will try and figure that problem out.

[Lv0f92yv]

After looking at this for a while longer, there is another problem that may be part of the recursion problem.

I amm adding nodes to the tree with the following calls:

bst.add( &Node( &HashedString( "firstHash", "firstPlain" ) ) );
bst.add( &Node( &HashedString( "HASH", "plain" ) ) );

Each HashedString object can print itself, defined as:

void HashedString::print()
{
	cout << "Plain: " << _plain << ", Hash: " << _hash << "\n";
}

When I construct the HashedString objects with the above add calls, the constructor is defined as such:

HashedString::HashedString( string hash, string plain )
{
	_hash = hash;
	_plain = plain;
}

What I don't understand, is when I print the HashedString objects using its print() method, I sometimes get output like this:

Plain: , Hash: firstHash

with the plain string empty. Sometimes both string are displayed properly... What could be causing this? Thanks...

Edit: Here is my bst.add() function, since I believe this to be the problem...

(Note this is called from bst.add( ... ) with _root as a second param)

void BST::add( Node* newNode, Node* check )
{
	//clean this garbage up please
	int comparison = newNode->_hs->getHash().compare( check->_hs->getHash() );
	cout << "COMP " << comparison << "\n";
	cout << "--------\nComparison Nodes: \n";
	newNode->_hs->print();
	check->_hs->print();
	cout << "--------\n";

	if ( comparison > 0 && check->right == NULL )
		check->right = newNode;
	else if ( comparison > 0 )
		add( newNode, check->right );

	if ( comparison <= 0 && check->left == NULL )
		check->left = newNode;
	else if ( comparison <= 0 )
		add( newNode, check->left );
}

Edit: The garbage comment was for me.

[Lv0f92yv]

I changed my calls to add to use the new operator when creating the node and hashedstring objects.

This causes each new Node object to have it's own spot in memory. Sorry for being so foolish... :[