Converting from Morse code is more difficult; however, there is in fact a straight-forward conversion.

Suppose we are hearing a sequence of dots and dashes. When listening to Morse code, you learn sequences of dots and dashes as representing specific characters. This requires a significant amount of practice. Suppose, however, you are listening or reading dots and dashes separated by spaces. Suppose you have a space, indicating that the next dot or dash is the start of a new character. Now, consider the following tree:

Suppose the first signal is a dot. This removes all possible characters in the right-hand sub-tree of the root. If the only signal is that dot, the letter was an 'e'. If, however, there is another signal, if it is a dot, we move down the left tree from 'e' and if it is a dash, we move down the right tree. We continue listening for either dots or dashes and continue down the tree. Now, one of three outcomes may occur:

• a sequence of signals goes down below the bottom of the tree, in which case, it is an invalid Morse code letter (for example, --..--..),
• a sequence of signals terminates at a location in the tree where there is a null character '\0', in which case, it is an invalid Morse code letter, or
• a sequence of signals ends at a place in the tree where there is a character, that sequence of signals indicates that letter.

For example, if you see .--. .- - . ..-., you start at the top of tree and

• go left, right, right and left and we are at 'p',
• go left and right and we are at 'a',
• go right and we are at 't',
• go left and we are at 'e', and
• go left, right, left and left and we are at 'l'.

If this was the end of the transmission, this would code patel.

This is definitely not how a human would learn Morse code, and it would be idiotic to try to do so. However, this would be perfect for a computer. The question is, how do we store and traverse such a tree?

Consider the following array:

You will notice that we are walking across the array following manner:

• the root is placed in array entry 1;
• the two letters in the next row, e and t, are placed in the next two entries of the array;
• the four letters in the next row, i, a, n and m, are placed in the next four entries of the array;

and so on and so forth as shown in this image:

Now, we will ignore array entry 0. Note that, for example, 'a' appears in the array entry 5. In the tree, its left child is 'r' and its right child is 'w'. These two are in array entries 10 and 11. Similarly, 'k' is in the array entry 13. In the tree, its left child is 'c' and its right child is 'y'. These two are in array entries 26 and 27.

Consequently, the children of the array entry n are in array entries 2*n and 2*n + 1.

We can now define the following process for decoding Morse code:

• Let $n \leftarrow 1$,
• Going through all signals in the input string in Morse code:
• if the next signal is '.', assign $n \leftarrow 2n$,
• if the next signal is '-', assign $n \leftarrow 2n + 1$,
• otherwise, if decode_array[n] equals '\0', then print a '*' as we did not have a valid Morse code letter, otherwise print decode_array[n]; and in either case, set $n \leftarrow 1$.

	char *decode_array[33]{"\0\0etianmsurwdkgohvf\0l\0pjbxcyzq\0\0"};

Acknowledgement

Albert Ndur-Osei suggested this project.