Correct implementation of Min-Max in a tree

Question

I implemented the min-max algorithm on a tree. The algorithm I created is working as intented, returning the path in the tree that corresponds to the min and max values. But my problem is that it doesn't feel right.
My question is , is that a correct implementation of the min-max algorithm?
I couldn't find a pure implementation of the algorithm in a tree structure that consists of nodes. On the examples I manages to find ,people implemented the algorithm to solve problems related to games (tic-tac-toe). To be honest I felt stupid I couldn't make the connection.
I used 2 functions ,
1->evaluations_function which traverses the tree and adds value to nodes that don't have (a.k.a. all nodes that are not leaves).
2->print_optimal which traverses the tree and returns the path .

public void evaluation_function(Node root, int maxHeight, int rootHeight) {
        if (root.childrenList.Count != 0) {
            foreach (Node node in root.childrenList) {
                evaluation_function(node, maxHeight, rootHeight);
            }
        }
        if (root.height != rootHeight) {
            if ((root.height % 2) == 0) {
                if (root.value < root.parent.value || root.parent.value == 123456) {
                    root.parent.value = root.value;
                }
            } else if ((root.height % 2) != 0) {
                if (root.value > root.parent.value || root.parent.value == 123456) {
                    root.parent.value = root.value;
                }
            }
        }
    }

And here is print_optimal

public void print_optimal(Node root) {
        int maxValue = 0;
        int minValue = 9999;
        if (root.childrenList.Count != 0) {
            if (root.height % 2 == 0) {
                foreach (Node child in root.childrenList) {
                    if (child.value > maxValue) { maxValue = child.value; }
                }
                foreach (Node child in root.childrenList) {
                    if (child.value == maxValue) {
                        Console.WriteLine("Selected node " + child.name
                            + " with value = " + child.value + " as MAX player");
                        print_optimal(child);
                    }
                }
            } else {
                foreach (Node child in root.childrenList) {
                    if (child.value < minValue) { minValue = child.value; }
                }
                foreach (Node child in root.childrenList) {
                    if (child.value == minValue) {
                        Console.WriteLine("Selected node " + child.name
                            + " with value = " + child.value + " as MIN player");
                        print_optimal(child);
                    }
                }
            }
        }
    }

I don't want to swarm the question with code , as my question is theoretical. But if you want to see the data struct or want to test the algorithm you can find it here : https://github.com/AcidDreamer/AI_Exercises/tree/master/1.2.1/Exercise1_2_1/Exercise1_2_1


IMPROVEMENT
evaluation_function changed to

public void evaluation_function(Node root, int rootHeight) {
        if (root.childrenList.Count != 0) {
            foreach (Node node in root.childrenList) {
                evaluation_function(node, rootHeight);
            }
        }
        if (root.height != rootHeight || root.childrenList.Count != 0) {
            int maxValue = 0, minValue = 999;
            if ((root.height % 2) == 0) {
                foreach (Node child in root.childrenList) {
                    if (maxValue < child.value) {
                        maxValue = child.value;
                        root.value = maxValue;
                        root.bestChild = child;
                    }
                }
            } else if ((root.height % 2) != 0) {
                foreach (Node child in root.childrenList) {
                    if (minValue > child.value) {
                        minValue = child.value;
                        root.value = minValue;
                        root.bestChild = child;
                    }
                }
            }
        }
    }

giving values to the current nodes.
print_optimal had a huge improvement using a bestChild field and is changed to

public void print_optimal(Node root) {
        if (root.bestChild != null) {
            Console.Write(root.name + "->");
            print_optimal(root.bestChild);
        } else {
            Console.WriteLine(root.name);
        }
    }

Answer 1

Overall your code is good (which you knew, since it works), but I have some remarks about improvements:

evaluation_function: you do not use maxHeight at all. Use it or remove the parameter. It's weird (kind of bad practice) that the function changes the parents of the current node. It should rather look at the children's values (if not leaf), and update the current node's value depending on that. Besides, you could add a field to keep track of the best child (or even of the selected path to a leaf) to avoid the matching process in print_optimal.

print_optimal(): You currently have a problem if 2 children have the same values: you'll print both of them and explore both trees. Checking if (child.value < minValue) { minValue = child.value; } is useless since you assume you've already used evaluation_function(), and it is not enough to "replace" evaluation_function if you had forgotten to do so.

Answer 2

I find it a little unnatural that the evaluation_function, which receives a Node as input, actually updates the value for the parent node.

I feel that a better approach would be for that function to update the current node instead.

It should do nothing if the current node is a leaf.

Otherwise, it should iterate through all the children (as it currently does in the first loop), and after each recursive call for a child, it should also check whether the current node value should be updated (i.e. a better value was just encountered, for the current child).

In addition, it is possible to add an additional field to each node, e.g. bestChild, or bestMove, to avoid re-iterating through children when calling print-optimal.