In this section, so far we’ve discussed a number of data structures. Specifically we’ve walked through: arrays, linked lists, stacks, and queues. Those structures are all in the linear family of data structures. This guide will introduce another type of data structure type: the tree data structure.

At the end of the day you will need to utilize tools such as arrays and linked lists in order to work with trees. So trees are not as much an alternative structure, instead they are a way of implementing and thinking about how data is organized. This is mainly because trees are another abstract data type (ADT). As you may remember an ADT means that there is no actual structure called a tree that we will use. Instead trees give us a set of processes to organize data so we can use it in our programs.

If you think that this sounds pointless to study, don’t tune out quite yet. As you go through these guides you’ll discover real world uses for trees that can literally improve an application’s performance exponentially.

Tree Data Structure Introduction

Definition

So what is a tree? A dead simple explanation is that a tree is:

A collection of elements with a parent/child structure.

If this seems a little vague let’s take a look at a basic tree.

Basic Tree Structure

Here is a basic tree structure. You can see that this example contains five data elements: 1, 29, 35, 42, 89. Each of the elements in a tree are called nodes.

If you’ve never worked with trees before let’s go through some of the common terms.

Root Node

The node located at the top of the tree is called the root node. In our example the 42 element is the root node. For binary search trees all of the elements to the left of the root node are less then the root node and everything to the right should be greater than. However that’s not a hard and fast rule for all trees. And in future guides we’ll discuss all of the most popular trees utilized in the design of algorithms.

Parent Nodes

Moving down the list you’ll see that our diagram shows that our example tree has two parent nodes. Essentially a node is considered a parent node if it has child nodes associated with it. In this case our root node is both the root and a parent node (which is the common pattern).

Child Nodes

Next on the list of tree elements are the child nodes. A good rule of thumb to remember is that all nodes in a tree are child nodes except for the root node.

Parent/Child References

One of the most important components of understanding how trees work is that a parent node has references to its child nodes. This is required since the only reason you would use a tree is to organize data in a way that you know how to access each element.

The Tree Data Structure and Recursion

Did you notice how our example seemed to have nested trees inside of it? The 29 -> 1 -> 35 data set had all the components necessary to be a tree. In this case 29 would be the root node and 1 and 35 would be the child nodes. In the study of algorithms you will come across a number of situations like this where large problems can be broken down into identical, smaller problems.

When this happens the algorithm or data structure is called recursive. We’ll have an entire set of guides dedicated to recursion, however for right now just know that an algorithm is recursive if it can call itself. For example, when we want to search for an element in a tree we don’t look at the tree like a big pile of data. Instead we simply look at a single parent/child relationship, and then we traverse through the tree running the same process over and over again.

Recursive algorithms are incredibly popular for both their performance and straightforward approach for solving complex problems.

Summary

I hope that this helps to give you a good idea on how to understand the basic tree data structure.

What's Next?

In the next guide we'll walk through the operations that are performed on trees along with some practical examples of how trees can be utilized in real world development.