Consider three items a, b, and c. Assume that we'd like to establish their order using comparisons. Naturally, there are 6 orders: abc, acb, bac, bca, cab, cba. Below is shown a diagram of an optimal decision tree for determining the order of these three numbers.

We observe that the height of the decision tree must be at least three levels deep to accomodate the 6 leaf nodes.

Imagine now that we have 4 items. How many different permutations are possible for 4 items? Equivalently, how many leaf nodes would there by in the optimal decision tree (which you should NOT attempt to draw)?