Binary Decision Trees

Question

I know the basics to a binary decision tree, but this problem has me a little stumped, and I'm looking for some verification on my ideas. The problem is:

"Create a binary decision tree that reflects the way a coin-sorting machine deals with standard US coins (penny, nickel, dime, quarter, half-dollar, and dollar). Hint: Look up diameters of each coin. "

I get that you start the tree off (the uppermost vertex) with where in the ordering the datum is. So, I suppose we could start the tree off with the coin that has the longest diameter and if it's not that coin, then we look for the 2nd longest? Vice versa until the end of the tree?

I think I understand the concept very well. How exactly would one construct this tree in terms of shape? Could it be linear? Or would it have to split off into right and left branches?

Answer 1

If you are allowed to have an unbalanced binary tree, the problem is as simple as comparing diameters on each level of the tree.

Level 1 (root): diameter(coin) >= diameter(dollar) ?
                  yes -> the coin is a dollar
                  no -> go to level 2
Level 2: diameter(coin) >= diameter(half-dollar) ?
           yes -> the coin is a half-dollar
           no -> go to level 3
...

Interpret the "yes" as going to the left branch on each level of the tree (which will always be a leaf), and the "no" as going to the right one. That way, you will end-up having an unbalanced binary to the right.