Trees

In this article, I am going to give an introduction to trees. Trees are unique data structures that are used to store data in a tree-like shape. They have many useful applications, which include 3D programs, data compression, Web browsers and even dictionaries. All in all, trees are wonderful data structures. Let's get started.

What are trees?

As I said, trees are a kind of data structure. If the phrase "data structure" is new to you, don't worry. It just means the way you represent data in the memory of a computer. So, trees are no more than a method for storing data in the memory of a computer. Which type of data? And when should we use trees? This is what we are going to discuss in a moment.

Trees look like the following diagram. First we have a root node which contains one item of data. The root node has some children,  and each one contains one item of data. Each one of the children, in turn, has some children, and so on...

In essence, it looks something like this:

 
Fig.1 An example of a tree

Now, you may find this pretty weird. Why would someone want to represent data that way? Let's assume we have a list of n numbers; what is the point of putting them in a tree? As we are about to see, there are some good reasons to do so. Additionally, in real life, there are several applications where trees are just the natural way to represent data.

First, before we go too far, let's look at some theory. Any tree can be represented by a tree where each node has a maximum of two children. This is called a "binary tree". A famous method to accomplish this is called "Left child, right sibling," but this is quite outside the scope of this article; check the further reading at the end of the article if you really need to know how to do it.

A binary tree looks something like this:

 
Fig 2. An example of a binary tree

Why did I introduce this? It has a very important implication. We don't need to study general trees in depth, since any tree can be represented as a binary tree. It makes sense then that, from now on, we will only focus on binary trees. As I said, we are not limiting ourselves, because any tree can be represented by a binary tree.

First, let's examine this fundamental problem: how can we represent a tree inside the computer memory?