Morse code

As a test, I was asked to write a morse code task where some of the signals weren’t able to be determined from the input. So in this case instead of having either the dot (.) or dash (-) we have a question mark (?) where it could be either a dot / dash.

Here is an image of the morse code alphabet of dots / dashes and here is a link to a view of the “tree” of the morse code of the dichotomic search, basically binary search of the morse code.

So, we are only going down 3 levels, below are some tests to confirm that the process is working fine.

  • .- = A
  • . = E
  • … = S
  • -.- = K
  • ? = ET
  • -? = NM

So, I approached this test by thinking that I need to have an “item” that stores the current value (e.g. character) and left / right item, and here is my item.h definition.

class item {
        char value;
        item *left;
        item *right;
        item(char value,item *left,item *right);
        item(char value);
        item(item *left,item *right);


        char getValue();

        item* leftItem();
        item* rightItem();

And then to build the 3 levels of the search tree

    item* head = new item(
        new item('e',
            new item('i', 
                new item('s'),
                new item('u')
            new item('a',
                new item('r'),
                new item('w')
        new item('t',
            new item('n', 
                new item('d'),
                new item('k')
            new item('m',
                new item('g'),
                new item('o')

and then the last part was literally reading in the signal to be processed and going down the tree either left / right or both for undermined signal.

string output(string signal, item* codes) {
    string ret="";
    if (signal.size() ==0 ) 
        return string(1,codes->getValue());
    for (string::size_type i=0; i < signal.size();i++) {
        if ('?' == signal[i]) {
            ret += output("."+signal.substr(i+1),codes);
            ret += output("-"+signal.substr(i+1),codes);
            return ret;
        } else if ('.' == signal[i]) {
            return output(signal.substr(i+1),codes->leftItem());
        } else if ('-' == signal[i]) {
            return output(signal.substr(i+1),codes->rightItem());
        } else {
            throw invalid_argument(string("Invalid character at this point of the string ").append(signal));
    return ret;

If you want to view the whole code, here is the link to the zip file of the morse code.