0
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's exactly what I had written down as scratch work. I figured I was overthinking this problem. Thanks for the verification! $\endgroup$
    – d3m0nxdrums
    Apr 21, 2016 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .