crecursionminimax

Why does my minimax algorithm not work properly?


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...


Solution

  • 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;
    }