Why does my minimax algorithm not work properly?

Question

I've made an algorithm that finds the largest number in a binary tree: (I know I should call the function "max" instead of "minimax", but It's too tedious to change it-)

I create a struct for every node and then link them together through the left and right pointers.

#include <stdio.h>
#include <stdlib.h>

// Struct for every node:
typedef struct treenode
{
    int value;
    struct treenode *left;
    struct treenode *right;
} treenode;

// Prototypes:
treenode *createNode(int value);
treenode *minimax(treenode *root);

int main()
{
    // Create the nodes:
    treenode *n1 = createNode(0);
    treenode *n2 = createNode(2);
    treenode *n3 = createNode(3);
    treenode *n4 = createNode(200);
    treenode *n5 = createNode(5);
    treenode *n6 = createNode(102);
    treenode *n7 = createNode(101);
    treenode *n8 = createNode(999);
    treenode *n9 = createNode(888);

    // Link them together:
    n1->left = n2;
    n1->right = n3;
    n3->left = n4;
    n3->right = n5;
    n5->left = n6;
    n5->right = n7;
    n7->left = n8;
    n7->right = n9;

    // Print the output of minimax():
    printf("%d", minimax(n1)->value);

    // Free the nodes:
    free(n1);
    free(n2);
    free(n3);
    free(n4);
    free(n5);
    free(n6);
    free(n7);
    free(n8);
    free(n9);
    return 0;
}

// Creates a new node in the tree, that isn't linked to anything:
treenode *createNode(int value)
{
    treenode *result = malloc(sizeof(treenode));
    if (result != NULL)
    {
        result->left = NULL;
        result->right = NULL;
        result->value = value;
    }
    return result;
}

// The minimax() function is recursive:
treenode *minimax(treenode *root)
{
    // If there are no "children" linked with the current node, return the current node:
    if (root->left == NULL && root->right == NULL)
        return root;
    // If there is only one child linked, minimax() this child and return the biggest value in it:
    if (root->left == NULL)
        return minimax(root->right);
    if (root->right == NULL)
        return minimax(root->left);
    // If the biggest value in the left child is greater than the biggest value in the right child, return the left child:
    if (minimax(root->left)->value > minimax(root->right)->value)
        return root->left;
    // If the biggest value in the right child is greater than the biggest value in the left child, return the right child:
    if (minimax(root->right)->value > minimax(root->left)->value)
        return root->left;
    // If the biggest values in both children are equal, return the left one:
    if (minimax(root->right)->value == minimax(root->left)->value)
        return root->left;
}

The program printed "2" instead of "999", not like I expected, but I can't find the error...

Answer 1

The maximum value could be stored in the root or anywhere in the left or right branches.

treenode *minimax(treenode *root)
{
    treenode *ret = root;
    treenode *temp;

    if (root)
    {
        temp = minimax(root->left);
        if (temp && temp->value > ret->value)
        {
            ret = temp;
        }
        temp = minimax(root->right);
        if (temp && temp->value > ret->value)
        {
            ret = temp;
        }
    }
    return ret;
}

Answer 2

This says it returns the right child but returns the left child:

// If the biggest value in the right child is greater than the biggest value in the left child, return the right child:
if (minimax(root->right)->value > minimax(root->left)->value)
    return root->left;

Answer 3

At least one problem is that you (sometimes) ignore the value of the current/root node.

Consider this:

treenode *n1 = createNode(1000);  // Notice this is the max value
treenode *n2 = createNode(3);
treenode *n3 = createNode(2);

// Link them together:
n1->left = n2;
n1->right = n3;

In the first call you'll get into this line:

if (minimax(root->left)->value > minimax(root->right)->value)
    return root->left;

In the two recursive calls you get into this line:

if (root->left == NULL && root->right == NULL)
    return root;

Consequently, the first call is actually the same as:

if (root->left->value > root->right->value)
    return root->left;

So you never ever checks the value of the root node. Therefore your code will give the result 3 but the correct result is 1000.

To solve it make sure to check the value of the root node as well.

BTW:

An even more simple test (that fails) is:

treenode *n1 = createNode(1000);  // Notice this is the max value
treenode *n2 = createNode(3);

// Link them together:
n1->left = n2;