Computing the Value of a minimax tree

Question

I am asked to compute the value of a minimax tree, which each node labeled with its initial value. I am just unsure how to do it. I know that it is a minimax tree if:

1. the root is a min node, the value of the tree is equal to the minimum of

   • The integer stored in the root
   • The value of the left subtree, but only if it is nonempty

   • The value of the right subtree, but only if it is nonempty

     2. If the root is a max node, the value of the tree is equal to the maximum of the above three values.

I was hoping someone can guide me in the right direction and help me understand this problem

Answer 1

I’ll get you started. Start at the bottom: the leaves have empty subtrees, so the value of each leaf is simply the integer stored in it. Now go up a level and work on the four max nodes just above the leaves. each of them is the root of a small tree with $3$ nodes. For the first one, for instance, we have this tree:

               0  
              / \  
             1  23

We’re dealing with a tree whose root is a max node, so the value of the tree is the maximum of $0$ (the integer stored in the root), $1$ (the value of the left subtree), and $23$ (the value of the right subtree). That maximum is $23$, so the value of this little subtree is $23$. Proceeding across, we find that the four subtrees whose roots are the max nodes at depth $2$ have values $23$, $99$, $98$, and $21$.

Now look at the left min node at depth $1$. The integer stored in it is $100$. We just calculated the value of its left subtree: that’s $23$. And the value of its right subtree is $99$. The minimum of these three numbers is $23$, so the value of the left subtree of the big tree is $23$.

Can you finish now?