Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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…

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>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;
}
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading