Binary Tree highest score

I have to create a very basic rudimentary game(without any visual or interaction element) for an assignment. I have to have a highest score function which returns the player node with the highest score, note that the score is not the player ID which is used to distinguish the node. This is my (very basic) code so far

Node* High_Score(Node* player, int max)
{
	if(player)
	{
			
		if(player->score > max)
		{
			max = player->score;
			cout<<max<<endl; //This is just to help me see what is the current max
		}
		if(player->left)
			High_Score(player->left, max);
		if(player->right)
			High_Score(player->right, max);
	}
	else return player;
}

I realise I could be missing something essential or have some code just plain wrong, the assignment is due tomorrow and I have spent long enough on this. Thanks for the help!

Gaminic (1621)

The Max in a Binary Tree can be found by just walking to the right son until NULL is reached (provided that Rson > Parent & Lson < Parent).

A simple while loop should suffice. I'm thinking something along the lines of:

1
2
3

Node* current  = root;
while (current->right != nullptr) current = current->right;
// 'current' now contains the maximum

Richardce (4)

But I'm not looking for the max, i'm looking for the node with the highest score, my node looks like this

struct Node{
	int playerID;
	char playerName[20];
	int score;
	Node *right;
	Node *left;
};

If I used your code it would only find the highest player ID

Peter87 (11234)

I don't think you need to pass max as a parameter to the function. You have to check the node returned from the call to High_Score on the child nodes. So in total you can have three nodes to choose from. player and the nodes returned from High_Score. Return the node with the highest score.

Peter87 (11234)

Gaminic (1621)

Is it useful the organize the tree by PlayerID? It seems more logical to do it by score, but it depends on what else you're going to do with it.

Anyway, I think the problem is that you're passing 'max' by value. Since the function changes the value of 'max', and changes should carry on through subsequent function calls, it should be passed by reference.

A small example:

void doubleItV(int max) { max *= 2; }
void doubleItR(int& max) { max *= 2; }
// Somewhere in main or so
int a = 50;
int b = 50;
doubleItV(a); // a is not changed, because passed by value
doubleItR(b); // b is changed, because passed by reference

As you can see, if you need a value to change because of a function call, you need to pass it by reference. Passing by value makes a temporary copy of the parameter and uses that throughout the function call.

Richardce (4)

Could you please show me an example Peter87?

Peter87 (11234)

I was thinking something like this:

Node* High_Score(Node* player)
{
	Node* maxNode = player;
	Node* n1 = High_Score(player->left);
	if (n1->score > maxNode->score)
	{
		maxNode = n1
	}
	Node* n2 = High_Score(player->right);
	if (n2->score > maxNode->score)
	{
		maxNode = n2
	}
	return maxNode;
}

(The null checks are missing)

Last edited on

Richardce (4)

Thank you so much!

Topic archived. No new replies allowed.

C++

Forum

Binary Tree highest score