Implement Tree Data Structure in Swift

You probably have already heard about the Tree data structure, or you might even have had a task in your interview where you had to implement it. This data structure is very useful and can be used to solve many programming challenges. In the present article, let’s cover the next questions:

• What is Tree data structure?
• What is it used for?
• How would one implement it in Swift?

Theory

I believe the simplest way to get an idea of how the Tree data structure looks like is through the following picture:

The Tree Data Structure

In the picture, we can see different names. Let me explain this terminology.

Root — in the Tree data structure the root is just simply the very first node. It is the same as other nodes and has a data field and fields with links to other nodes. It just happens to be the first.

Node — is a block of data that the Tree data structure contains. It has a value and fields with links to other nodes.

Leaf — is a node without any children. It is also referred to as an external or terminal node.

Now, let’s cover when the Tree data structure may come useful:

• It is used to represent hierarchies or to put it simply, to reflect structural relationships in some data.
• Trees provide very efficient and quick searches as well as insertions.
• It also can provide sorted lists of data.

There are many more other advantages of trees that allow them to solve different types of problems very efficiently. There are also different types of trees for various problems. For example, one of the most popular ones is the Binary Tree data structure.

Implementation

Now, when we understand the required terminology, let’s finally implement our own Tree data structure in Swift.

The Tree data structure is made of nodes. So, the first step is to create it. Our node is going to hold a value and also have links to its children. For the latter, we are going to use an array.

We will create an initializer that takes a value and children nodes if they do already exist, otherwise it will be initialized with a value and an empty children array.

It can be handy sometimes to have a link to a parent node. This is optional, but you can add it as well. We also marked it as optional and weak. The former is because not all nodes in our tree will have a parent, e.g. root node. And we use weak because if our parent node will have a strong reference to its child node and its child node will have a strong reference to its parent node, we will accidentally create a strong reference cycle where we will end up with a memory leak. And we do not want that, right?!

Now, let’s add the function that will allow insertion to the tree. This method will append new child node to the children array and assign self to its parent.

Implement Search

Now, let’s touch on something more interesting and implement search to our tree.

Let’s break the explanation in three steps:

• First, we check whether the value we are searching for is equal to the value of the current node, and if it does, we return it.
• If not, we go through every child node and recursively call the search method until it finds the value we a looking for.
• If the value was not found in a tree, then we return nil, meaning the absence of the value.

And that’s pretty much it. As a challenge, you can conform to the CustomStringConvertible protocol to be able to print your nodes’ values in the console in a way it will be easy to understand the hierarchy of the tree.

Summary

Congratulations on making it to the end! You have done a great job and implemented your first own tree.
The are many other tree data structures, and I encourage You to look at some of them.

Thanks for reading!

if you enjoyed this article, be sure to give it a clap so others will find it more easily.