How Tree Data Structures Help Us Understand Morse Code
When you talk to a normal person about trees, they’ll imagine, well, actual trees. Maybe they’ll think about a great oak, or a pine tree, or a Canadian maple as its leaves whisper with the breeze on a quiet autumn afternoon.
When you talk to a programmer about trees, they’ll think of data structures. They’ll think about crafting optimal binary search trees, clever traversal methods, and complex algorithms.
This is why you can’t have a normal conversation with a programmer.
What is a tree data structure?
In programming, you have data. When you have data, you need a way to organize it. If you organize it properly, you can later access it easily. If you don’t, it’ll take forever to find what you’re looking for.
To help organize our data, we use data structures.
An example of a basic data structure is an array. You can just think of it as a list, like this:
["Alice", "Berk", "Cory", "Debrah", "Elizabeth"]In an array, we have a bunch of values listed one after the other. It’s a naturally sequential way of arranging data. If the data we’re trying to store is sequential (like the alphabet), then this works great.
But sometimes we have values that are related to each other in non-sequential ways. Like types of organisms. You wouldn’t represent that like this:
["Animals", "Mammals", "Cows"]Instead, it has a hierarchical structure with multiple values (ancestors, etc.) occupying the same level. So it looks more like this:
To represent such data, we use what’s called a tree data structure.
Just as the name suggests, this type of data is represented as a tree. It has a root, nodes, edges, and leaves.
This type of structure allows us to do some pretty cool things, which are not possible to do with linear structures like arrays.
Planting our trees in the real world
There are different types of tree structures that are useful for solving different types of problems. This topic is quite broad, so I won’t get into too many examples. But if you’re interested, I put some links at the bottom of the article which go into much more detail.
One example of a tree structure in the programming world is the DOM tree. DOM, or the Document Object Model, is a representation of the HTML elements in a website. That’s right, the HTML structure of all the websites we visit is set up using a tree.
This allows programming languages like JavaScript to find specific elements on the page and manipulate them. It also makes possible neat functionality like parent/child relationships and inheritance.
Another real-life application of a tree structure is to design “choose your own adventure” games. Say we have a game that prompts a decision from you on each step, and your decisions determine the eventual outcome of the game. It could be represented like this:
You could recognize this as a series of if/else conditionals. If I take this path, I end up here. Otherwise, I end up there. It’s also an example of a binary tree.
A binary tree is a special type of tree where each node can have at most 2 children. As in, from each node, I can either go to A or B. Left or right. That’s it.
This reduction of complexity results in a data structure that is highly efficient in finding what we’re looking for. Instead of looking at every node in the tree to find something, we’re able to take a direct path to our destination.
Not every form of data can be represented as a binary tree, but it still has some really interesting applications.
One of those applications is, you guessed it, decoding Morse code.
What does it mean to “dot dot dash”?
You might have heard of Morse code before. It probably sounded something like: “beep, beep, beeeeep, beep”. And maybe your weird uncle went: “Oh, that’s interesting news”.
To us normal people, Morse code sounds uninteresting — even irritating, perhaps. But the fact is, since its inception almost 200 years ago, Morse code has been used by countless sailors, pilots, and communication specialists to send messages over very simple transmitters.
The way Morse code works is each letter of the alphabet is represented as a combination of “dots” and “dashes”. For example, the letter A is “.-“ The letter R is “.-.”
Now, before you go memorizing the dots and dashes of all 26 letters, as it turns out, there is a method to this madness.
If you think about it, if we simply had a list containing each letter and its Morse code representation, we would have something like this:
{
"A": ".-",
"B": "-...",
"C": "-.-.",
...
}Then when we received a message, we would have to go look at each letter in the list to see if it matches the dots and dashes we got. This is a tedious task, both for humans and computers. There has to be a more efficient way to do this.
And thankfully, there is. You see, the Morse alphabet can be represented as, that’s right, a binary tree!
It looks like this:
The smart people who created Morse code organized the letters very cleverly. Each letter starts with either a dot, or a dash. Then it could follow with another dot, or a dash. And so on. We can traverse the binary Morse tree by following the appropriate path from each node. This allows us to take the most direct path to our encoded letter.
Let’s see an example of how using a binary tree structure makes the decoding process simpler. Say we receive a message that says “- -..” How can we decode this message?
We’ll start at the top, and go with the “dash” path. Then we’ll go “dash” again, then “dot”, and finally “dot” again.
The letter is “Z”, we decoded the message! And we only had to look at 3 other letters on our way, as opposed to going through all 26.
This was easy even for a human to do, so imagine just how fast a computer can use a binary tree lookup to find what it’s looking for.
When you’re decoding just a few words, it might seem like it wouldn’t be such a big deal to go through a linear list each time. But when you’re dealing with pages and pages at a time, having your Morse code in a binary tree like this will make all the difference in terms of decoding speed and efficiency.
To tree, or not to tree
As it turns out, trees are awesome both in nature and in our data structures.
However, there are tons of ways to structure data and there is an entire branch (no pun intended) of computer science that is dedicated to such problems. In this article, we learned about what the tree data structure is and how it can be used to solve a real-life problem.
Whether a tree structure is useful or not depends on the problem at hand. If the data we have is of some sort of hierarchical nature, then it makes sense to use a tree. But if we instead have sequential data, or data that is interconnected in more complex ways than a simple hierarchy, then we would have to use some other type of structure that is more suitable.
At the end of the day, the old proverb holds true: See the forest for the trees. When you see data that is hard to represent and organize with linear structures, ask yourself, could I use a tree to make my life easier?
And while you’re at it, maybe go out and plant a tree. Because you know, they give us oxygen so we don’t die. They’re pretty cool.
If you would like to learn more about this topic, check out these awesome resources:
- Everything you need to know about tree data structures, FreeCodeCamp
- Video: Introduction to trees, mycodeschool
- Tree applications, Greg Baker from Simon Fraser University
- Morse code, Wikipedia
