C++ Binary Tree Maximum Value function

[krizam]

Hello -

I cannot figure out why this binary tree max function will not work correctly, when i try to run this function the program crashes Note: This is to be done without having the binary tree ordered in anyway

template <typename T>	
tnode<T> *max(tnode<T> *t)
{
	
	// we will return maxValPtr
	tnode<T> *maxValPtr,*leftMax, *rightMax;

	
	if (t == NULL)
		maxValPtr=NULL;
		
	else
	{
		// temporarily assume t is pointing to the maximum
		maxValPtr=t;
		// leftMax points to the maximum value on the left subtree
		leftMax=max(t->left);

		// if leftMax is not NULL and the value to which it points
		// is larger, change maxValPtr
		if(leftMax!=NULL&&leftMax->nodeValue>maxValPtr->nodeValue)
		{
			maxValPtr=leftMax;
		}

		// rightMax points to the maximum value on the right subtree
		rightMax=max(t->right);
		// if rightMax is not NULL and the value to which it points
		// is larger, change maxValPtr
		if(rightMax!=NULL&&rightMax->nodeValue>maxValPtr->nodeValue)
		{
			maxValPtr=rightMax;
		}
		
			
	}

		return maxValPtr;

	// return a maxValPtr points to the node with maximum value for the tree
	
}

This is the full code for the whole thing if you want to look at it:
http://studentweb.uwstout.edu/clouti...rytreemax.html

Any help would be appreciated

[jonnin]

You should re-write this thing.

It looks like, from a tired person's eyes, that the thing iterates over all the guys but replaces with NULL on every leaf!!

Its doing a traversal that looks good in the else area, but EVERY time you hit a null pointer, you lose the value of max and replace it with null. Oops??

[Code_Nerd]

I have done a similar program but not with templates. I used Linked lists to implement my binary Tree.. Anyway you may get some tips from this? It can be done recursively..

 getRightmostData()
              { if(right == null)
               return data;
          else 
              return right.getRightmostData(); }

I did this Java and just tried to roughly convert it over for you.. :)

[jonnin]

His is recursive too.
and that doesnt look correct either? The if/else seems bad, won't this just return
the deepest data (his list is not in order remember)?

It reads:

if your on the deepest one,
return data (how do you know this ones the largest)
else
go deeper //you dont check these values if right is not null, which it isnt on the way back up the stack.

[Code_Nerd]

Yes you are correct, I didnt realise his list was not ordered..

My apologies for not reading the whole thread!