Swift 3 Enums and Binary Trees

Algorithms and Enums — YEAH!!!!

I remember starting to learn Binary Search Trees and being all like: ‘this is impossible’. They aren’t really that bad, they are also super common and useful. So let’s get started: YEAH!!!

In this tutorial I’m going to use Swift enums, pattern matching, indirect cases, generics and switch statements. If any of these are unfamiliar, hang in there, I’m going to teach all of these in the latest Swift 3 syntax shortly. I’ll explain as I go along though and remember all of the source is available for playing with on github here.

Something that really helps when learning algorithms and data structures is a visual guide — don’t underestimate how much this matters!

Let’s take a look at a visual concept of what we’re trying to make here:

Green lines, circles and numbers… How hard can it be?

We’re going to make a data structure where numbers are stored in nodes (circles) and inside of each node route, any number smaller than it is going to be a child to the left, and any number greater than it is going to be a child to the right.

So the parent node will be a number, the child node will branch to the left if less than the parent and to the right if greater than the parent.

Also, if there are no children this is like a little leaf, left hanging on its own.

Leaf — Yeah!!!!

Just before we start, we’re going to create a way to make nodes and a way to search to see if a node exists. We won’t be checking for duplicates or deleting nodes but you can do that on your own if you’re needing something for kicks.

Let’s do this:

enum BinaryTree<Element> {
}

Here we have created an enum -> an enum is like a list of items. The cool thing is, we can only be in one state at a time from that list. For example:

enum Moods {
case Happy
case Excited
case FeelingStoked
}

This somewhat inspirational list above can only be either Happy, Excited or FeelingStoked. You can’t be in two states at once. Take your pick, I’m currently: Moods.FeelingStoked

Back to our example above. You’ll notice in the BinaryTree enum that we have these weird things after the declaration with <Element>. In Swift, we have to tell the enum what kind of data it is going to be handling when we create an instance of it. We might want to create one that handles Integers, or maybe Strings, but then we’d have to make several versions. If we create a generic parameter though, then we can just create one with whatever we want and Swift will be like: ‘Oh cool, so you gave me an Int here. That’s cool, I see what you’re doing here; Ints it is’. Now we can just create one like a mini blueprint and make it easier to use it for every type.

BREATHER

Okay so you’ve just learned about enums which are lists that can only be in one state at a time and also generics which are great for flexibility in our code. Lets create our cases now.

Our nodes can be either empty or have a value.

If our node has a value, does it have a child on the left? If not then the left will be empty.

Also does it have a child on the right? If not then the right will be empty.

Here’s another glance:

Notice the leafs at the end in 1, 4, 6, 8, 12, 14

So we only need two cases: empty and node — no value or a node with a value :D

enum BinaryTree<Element> {
case empty
case node
}

Yay! Looks okay right?

How do we make nodes then? Well, we’re going to use a handy feature in Swift called pattern matching. Look at the example first:

enum BinaryTree<Element> {
case empty
case node(value: Element, left: BinaryTree<Element>, right: BinaryTree<Element>)
}

Let me explain this clearly. The empty case is still the same which is great. However now we have a few associated values (values associated with this case) with the case node. This can look weird at first, but just think: ‘If I have a node then it has to have a value (maybe 9 or something), it also needs to have a left node and a right node. Those nodes could be empty, they could have their own value.

So in fact these values make sense right? We need these values if we’re going to have a node so you can just plug them in right there when you create a node.

Notice that the left and right parameters are also of type BinaryTree. Also notice that you have a giant RED ERROR now! Noooooo! Wait, its easy to fix.

XCode is saying: ‘Hang on, if I am going to make this enum, I need to know exactly what size to make it. That is the deal! But if you have a BinaryTree inside a BinaryTree, then that BinaryTree could have 1000 BinaryTrees in it. So how can I possible know what size to make it?’

So the compiler needs to know the exact size of an enum and we can’t know that for sure as it will change as soon as we add a node on so we can simply give it some space in memory and just point to it with the ‘indirect’ keyword. Think of this as a compromise between what you’re asking and what the compiler needs to press on.

enum BinaryTree<Element: Comparable> {
case .empty
indirect case node(value: Element, left: BinaryTree<Element>, right: BinaryTree<Element>)
}

One last thing: if we’re going to be comparing left and right they need to be able to be compared (duh, that sounded simple) so we simply conform to the comparable protocol — no compiler errors!

Indirect enum cases are so coooooool! Wait, where am I?

Awesome we’re ready to write a function that adds a NODE.

extension BinaryTree {
func addNode(_ newValue:Element) -> BinaryTree<Element> {
   }
}

Here we’ve written a neat extension to our BinaryTree enum which will take in a value (an Integer in this case) and will return a whole new tree rather than change our existing tree.

First. Let’s figure out if the node we’re in is empty or not. Switch time!

extension BinaryTree {
func addNode(_ newValue:Element) -> BinaryTree<Element> {
      switch self {
      case .empty:
      }
   }
}

‘self’ here is the BinaryTree. It’s saying ‘Hey am I myself empty?’. If so, then we know we can simply insert our node with empty left and right values because it will be a leaf. If it wasn’t empty then we’d have to… well, we’ll do that in a minute.

extension BinaryTree {
func addNode(_ newValue:Element) -> BinaryTree<Element> {
      switch self {
      case .empty:
     return BinaryTree.node(value: newValue, left: .empty, right: .empty)
   }
}
}

We simply return a BinaryTree with a node which will contain our value (say 2) and empty cases for right and left!

Finally let’s take care of the case that there might be a node there already. If there is one, we’ll want to check if our new number we’re inserting is larger or smaller than the current node so it can go on the left or right. You’re almost there!

extension BinaryTree {
func addNode(_ newValue:Element) -> BinaryTree<Element> {
switch self {
case .empty:
return BinaryTree.node(value: newValue, left: .empty, right: .empty)
case let .node(value, left, right):
if newValue < value {
return BinaryTree.node(value: value, left: left.addNode(newValue), right: right)
} else {
return BinaryTree.node(value: value, left: left, right: right.addNode(newValue))
}
}
}
}

To explain the returns here, you’re checking if the newValue is less than the existing value in the node. If it is we then run the function again inside the node and it will check again if it is smaller or greater. If it is it will run it again and so on… Until it finally becomes a leaf with no children. Running functions repeatedly like this inside of functions can nip your head a bit at first, but if you think about it we need to insert it at the end of the tree so it’s got to start at the top and find the correct path all the way down.

Also the new value will go to the right if it is greater than the existing value.

To finish up I just want to say that if you have understood BinaryTrees here then congratulations. There is however one small type of strange-looking Swift sorcery going on in the above code:

case let .node(value, left, right):

This is called ‘pattern matching’ where we create temporary variables representing the values already there. Then we can just work with those argument names (sort of like closures where we name the objects we receive back).

Let’s make one!

let tree = BinaryTree<Int>.empty

Here you intialise a BinaryTree called ‘tree’ and start it as empty.

Let’s add a node on!

let tree = BinaryTree<Int>.empty.addNode(3)

Congratulations, you’ve just nailed BinaryTrees!