Decisions, Decisions

This problem defines how to represent a boolean function by a tree (in a rather convoluted way, I may add), and asks what is the minimal tree to represent a given function.

The limit of 18 variables, or 2^18 nodes in the tree, means that the creation of the tree must be done in linear time.

If the tree did not have to be minimal, we could simply build the tree from left tor right, since the input ends up going in the same order the leaf nodes do. The reduction rule is pretty straight forward. We can reduce a subtree to a single node if every leaf in that subtree has the same value. This gives the recursive algorithm:

• recurse(x) returns number of nodes in the reduced subtree. If they are all the same, also return the output value.
• recurse(left)
• recurse(right)
• if left value == right value, return 1 (we reduced this subtree) and the value
• else return left count + right count + 1