Trees! Trees Everywhere! Much like the Ents in Lord of The Rings, this data structure was one of the first non-linear ones to appear and given its incredible versatility and adaptability, it has maintained relevance for decades.
In computer science, as you might recall, a tree is a very functional data structure that can be used to model a wide range of hierarchical information sets such as decision trees for game logic, file systems, and organizational charts. More advanced tree structures are used in image processing, geospatial indexing, searching (mapping), and form the backbone of most database and hashmap structures.
It is the simplicity of the tree that gives it superior performance with some specific trees capable of O(logn)
time complexities across all four major procedures (search, sort, insert, and delete).
The core structure of the tree is the node, a simple data structure that we have used in with Linked Lists and Queues. We will build upon its versatility by putting together many nodes to grow our trees.
Throughout this lesson, we will create a Tree data structure that is capable of insertion, deletion, traversal, and printing. In the end, you will be given some challenges to increase the capability of our tree.
Let’s get started by taking a look at our Node class from the previous lessons and refactoring it into a TreeNode
class to set the stage for our Tree.
Instructions
In Tree.swift, you will find the Node
class that we built in previous lessons. The first thing to do is rename it to TreeNode
. Our new TreeNode
class will need to keep track of our children using an Array. We’ll also have no more need to track which Node
is “next” since we can have multiple children, not just one Node
.
In the TreeNode
class:
- Rename the class from
Node
toTreeNode
- Delete the instance variable,
next
- Create a new instance variable,
children
with the type being an Array ofTreeNode
s.
Don’t worry about the initializer error after you’ve completed these steps, we’ll deal with that in the next instruction.
Refactor the constructor to instantiate children
to an empty Array
. When you first create a TreeNode
, you want it to have no children (a leaf node).
Now let’s test the changes we just made to check for errors. Outside of the TreeNode
class, instantiate a new TreeNode
variable with the name root
with the String
, “Planting my first seed!” as the data
.
Print out the root
’s data
property using the print()
function. We’ll create a better print method in the lessons to come; For now, we just want to see our tree growing!