Trees: Swift

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.


Planting Deep Roots

So far, we've had to use some workarounds to visualize the tree. For example, we’ve printed the count of `children`, printed its `.isEmpty` status, and printed the results of our custom `==` method. Wouldn’t it be nice if we could actually print the tree in a way we can see what’s in it?

To accomplish this, you'll conform `TreeNode` to `CustomStringConvertible`. Recall that this protocol has a single property, `description`, that can be customized to represent your class in any way you see fit. You will build a string inside of the property and then return the completed string as the property value.

Go ahead and run the program and see how our TreeNode prints by default. Pretty useless, eh?

Let’s add the protocol conformance now!


Printing a TreeNode

Don’t worry, this section won’t be on the quiz, but we wanted to give you an example of how you can take your basic Tree data structure, which only allows Strings as a data type, and convert it into a generic Tree class. In other words, a generic Tree is one that can have nodes of any data type, so long as they are all the same type in a given tree.

With little change to the code base, the Tree now supports a wide range of data types (`String`, `Int`, `Float`, `Double`, `Character`, etc). You can copy the code and play around with other data types as well in your own IDEs off platform. Try `CGColor` or `Bool`, what do you need to do to make those data types work? 

Hint: Conform to another protocol, specifically `Comparable`.  If you add other data types, consider how they will be printed… Do you need to add another extension of `CustomStringConvertible` to display useful information?

While some of these ideas may seem deep down the rabbit hole, showing that you have at least thought about these kinds of situations or have at least conceptual familiarity can help set you apart from your peers during an interview.


Going Generic: Accepting Any Data Into Your Tree

You’ve learned how to climb from the top to the bottom of the tree, exploring all the leaves first before climbing back down each level. Now let’s learn how to explore each level (depth) of a tree before moving on to the next level, eventually reaching the leaves.

Traditionally this challenge is tackled using a Queue. As you recall from our lesson on  Queues, it is a linear data structure following a First-In-First-Out (FIFO) protocol. For this exercise, you will be using an Array to replicate the queue and taking advantage of the Array method `removeFirst(_:)` to follow the FIFO logic instead of adding your own Queue class.

Breadth-first traversal starts by adding the root to the queue, then it enters a while loop that runs while the queue is not empty. Each iteration of the while loop starts by dequeuing the first element off the queue and ends the loop by adding the children of the dequeued node to the end of the queue. In between those two actions, the dequeuing and the appending, it is up to you to decide what action to take. In this exercise, we will simply print out the node that was dequeued so that we can follow the logic of the traversal.


Climbing (Traversing) The Tree: Breadth First

If you look back, all of our work has been exclusively in the `TreeNode` class, in fact, we haven’t even defined a `Tree` Class yet, but this is where we will create our actual `.print()` methods.

There are two functions we will create, a generic `.print()` method that we will use to print the whole tree and a `.printFrom(_:_:)` method that will allow us to provide a specific entry point into our tree and print from there. The `.print()` method will simply call the `.printFrom(_:_:)` method using the root as the entry point.

Similar to the `.removeChild(_:)` method, the `.printFrom(_:_:)` method will use recursion to iterate through all the elements of the tree.
If you look at the **Tree.swift** file, you will see that we’ve added the `Tree` class to the bottom of the file. It is a simple structure that has only one property, the `root` of the tree. We’ve also reduced the information in the `TreeNode`’s `description` variable so our printing is easier to read. We've also made some changes to our `CustomStringConvertible` extension and other minor updates.


Printing The Tree

What good is a tree if we can’t climb it? In general, there are two ways to climb a tree:
- Depth-First Traversal: climbing from the root and following each branch down to its leaves
- Breadth-First Traversal: climbing all the branches on the same level (depth) before moving to the next level.

Actually, we’ve already been doing Depth First Traversal in both the `removeChild(_:)` and `printFrom(_:_:)` methods. The recursive steps of each of those methods follow the same logic:
1. Grab a node and do something (like print it)
2. If that node has children, call this method for each child and continue until you reach a level with no children

There are several different ways to implement a depth-first algorithm; we will tackle a “pre-order” traversal. This method is great at providing a topographically view of our tree so we can visualize the structure. The two other methods are:
1. Post-order, in which we begin with children and visit parents sequentially (not quite as simple as this) 
2.  In-order, which we will implement in our binary search tree in an upcoming lesson, and returns the nodes in sequential order (assuming we have defined what one node being greater than the other node means).

We will create a method, `depthFirstTraversal()`, that will move through the tree in this way. We will start by simply printing the data of each node so you visualize the traversal. However, in the end, we can modify the code to have it perform any task you want on the nodes. 


Climbing (Traversing) The Tree: Depth First

Great work on building your first non-linear data structure! The fundamentals you learned here will be instrumental in your success, not just in this course but also as you apply your skills in the practical world. Let’s go over a few of the central topics we reinforced through the lesson:
- A tree contains nodes, specifically:
- A root node
- Branch nodes
- Leaf nodes
- Branch nodes have children
- Leaf nodes do not have children
- We can traverse a tree either depth-first or breadth-first
- We can define equality by implementing the `Equatable` protocol and define what `equal` means to our classes.
- We can change the way Swift prints a class by implementing the `CustomStringConvertible` protocol and defining what data to return as the `description` variable.

As a challenge, what other methods and functionality can you add to make your tree more functional? We thought of a few if you want to challenge yourself:
- Modify our TreeNodes and the `==` method to refine equality. If you remember the Poe Family Tree, we still found a way that we could delete people by accident
- Add a property to the tree that returns the depth, or how many levels deep, the tree is. This is useful in a number of searching and sorting algorithms.
- Add a `find()` method that returns an element if it matches the search criteria
- Add a `parent` property to TreeNode so you can also traverse the tree from leaf to root. Remember not all nodes have parents (the root node) so it will have to be an optional, much like in a LinkedList or similar linear structure.


Planting a Forest: Review and Expanding Capabilities

Logically, after creating the ability to add children to your tree, the next step would be to write code that also removes children. To accomplish this functionality, we’ll need to take a few necessary steps, the first being how to determine equality among TreeNodes.
It does us no good to ask our program to remove a specific TreeNode if we have no way of identifying that node within our tree.

Swift provides a protocol for just this purpose, `Equatable`. A type that conforms to the Equatable protocol can be compared for equality using the “==” or “!=” operators.

These types of operators are known as [infix operators](https://docs.swift.org/swift-book/LanguageGuide/AdvancedOperators.html), as they typically sit between two targets. You use many of them all the time (`+`, `-`, `*`, `/`) and most can be overloaded, meaning we can define specific functionality for them in our classes. For example, we could define the `+` function in our `TreeNode` class to “add” one TreeNode’s data String to another. It might look something like:

```swift
extension TreeNode {
  static func + (left: TreeNode, right: TreeNode) -> String {
   return left.data + “ “ + right.data
  }
}
```
Now, if we were to create two TreeNodes, we could “add” them and print the result.

```swift
var branch1 = TreeNode(data: “I’m node 1 ”)
var branch2 = TreeNode(data: “and I’m node 2.”)
print(branch1 + branch2) // Prints: “I’m node 1 and I’m node 2.”
```

In order for our TreeNode to become Equatable, we need to define what equality means to us:
- Both TreeNodes have the same `data` value
- Both TreeNodes have the same `children`

This is truly tree-specific and different situations will call for different definitions of equality. Your end product will be a family tree, and it is possible for a family to have two people named the same. By also checking to make sure that the children are equal, we can remove the right person from the tree (most of the time).


Apples to Oranges

Sometimes, our trees can grow a little out of hand with branches and leaves that we don’t want anymore. Now that we’ve defined equality in our TreeNodes, we can start the process of pruning out any unneeded information.
Our pruning process will be recursive in order to work our way down every branch and leaf of the structure, and it will also take advantage of some of the built-in Array methods already included in the Swift library.
As with all recursion, the first step is to identify our base case to return out of. In our case the base cases will be:
- The `TreeNode` has no children, so return out of the method
- The `TreeNode`’s children contain the item to remove, so remove the child and return

If neither of those cases is true, we call the `removeChild(_:)` method on each `child` in the list of `children`.


Pruning The Tree

Now that we’ve built out the structure of the TreeNode, let’s add some functionality! The first step will be to add children to our TreeNode, what good is a Tree if we can’t grow branches!

We want to create two variations of the `.addChild()` method, one that accepts a complete `TreeNode` as an argument and one that accepts a String as an argument and then creates a `TreeNode` from that String. This technique, also called _function overloading_ (or method overloading, depending on your programming language), is the practice of creating multiple instances of a function with different parameters and/or return types. You’ll run into this practice quite often as it serves a variety of roles, from making your code easier to use to allowing you to encapsulate (hide from the user) certain internal functions of your program.

If it only takes a dozen lines of code or so to give the user an easier way to create something, in our case just providing a String instead of creating a whole new `TreeNode`, it is worth the extra time spent to have a happy customer, even if that customer is you.

Note: In some use cases, trees may also include a reference to their parent node, however, in our implementation of a tree, we will not have any need for this property and omit it completely.
