NEW: Subscribe to Hacking with Swift+ and accelerate your learning! >>

< Back to Latest Articles

Trees

Trees are an extraordinarily simple, extraordinarily useful data type, and in this article we’ll make a complete tree data type using Swift in just a few minutes. But rather than just stop there, we’re going to do something quite beautiful that I hope will blow your mind while teaching you something useful.

Watch the video here, or read the article below

If you’d like to follow along with this tutorial, create a new macOS command-line app in Xcode.

The basics of trees

A tree data structure is one where a single root object has several children, and each of those children can have their own children, and so on. We give it the name “tree” because a tree has a single trunk at its base, then has several thick branches coming off that trunk, and many smaller branches coming off those, and so on.

Each object in the tree holds its own value, such as an integer or a string, as well as an array of its children.

It’s common to hear some specialized terminology with trees:

  1. The root object is where your tree begins, like its trunk.
  2. A branch object is one part of your tree that has more branches coming off it.
  3. A leaf object is one part of your tree that has no branches coming off it.

All three of those – root, branch, and leaf – are generally just called “nodes”, because although in practice they have different configurations they ultimately they are the same thing: a single value, plus an array of children.

Some people like to have a separate Tree structure that has a root node property, but that isn’t necessary – if we make all three parts of our tree the same type then it becomes possible to carve off subtrees just by referring to a specific node in the tree.

Enough talk, let’s build a basic tree. We want this to hold any kind of value, so we can make it generic like this:

struct Node<Value> {
    var value: Value
    var children: [Node]
}

That already works, but with a couple of small changes we can make it much nicer.

First, that children property is exposed to the world, which means anyone can manipulate it freely. Sometimes that’s what you want, but it’s usually better to have control over this sort of thing so you can add logging or other functionality in one central location.

So, we can make children read-only for external users, while keeping it modifiable for methods inside Node:

private(set) var children: [Node]

Now that writing to our array is private, we need a simple method to add children externally:

mutating func add(child: Node) {
    children.append(child)
}

Second, the synthesized memberwise initializer for Node requires us to pass both a value and a children array, but when we’re creating nodes often we don’t want to pass in any children at all.

We can make this much nicer by adding two custom initializers: one that accepts just a value, and one that accepts a value and an array of children. Both of these will use no external parameter label for the value, because I think it makes creating nodes more natural – we would write Node(5) rather than Node(value: 5).

Add these two to Node now:

init(_ value: Value) {
    self.value = value
    children = []
}

init(_ value: Value, children: [Node]) {
    self.value = value
    self.children = children
}

And that gives us a pretty good first pass at a tree – we can now create some nodes that model part of my family, and connect them up:

var andrew = Node("Andrew")
let john = Node("John")
andrew.add(child: john)

var paul = Node("Paul")
let sophie = Node("Sophie")
let charlotte = Node("Charlotte")
paul.add(child: sophie)
paul.add(child: charlotte)

var root = Node("Terry")
root.add(child: andrew)
root.add(child: paul)

Because these are all structs, Swift does a pretty good job of printing them out neatly. For example, we can print everything from the root:

print(root)

Or just print out one branch:

print(paul)

Making it more useful

To make our tree genuinely useful, we need to add at least three things to it:

  1. The ability to compare one node against another, so we can tell if two nodes have the same value and children.
  2. The ability to know the size of the tree, telling us how many items in total it is.
  3. The ability to find a specific node in the tree, if it exists.

I’ve arranged those tasks from easy to hard, but to be honest none of them are that challenging – like I said at the beginning, trees are extraordinarily simple things!

First, if we have two nodes that are identical – i.e., they have the same value and have children that are also identical – then we should be able to use == with them to get back true or false. This needs to check all children, all grandchildren, all great-grandchildren, and so on, so that one entire tree is compared against another.

That might sound like a lot of work, but actually it’s effectively no work at all: we can tell Swift that Node conforms to the Equatable protocol as long as the value type it’s storing also conforms to Equatable, and, well, that’s it. Thanks to conditional conformance, Swift will take care of the rest of the functionality for us, so we just write an empty extension.

Here, try it out now:

extension Node: Equatable where Value: Equatable { }

Literally no code in there; Swift is doing everything. And yet already we can write code like this:

print(paul == andrew)
print(paul != andrew)
print(paul == paul)

Isn’t that just amazing?

But why stop there? We can also make our nodes hashable if their values are washable:

extension Node: Hashable where Value: Hashable { }

We can even make them codable using the same approach, allowing us to encode and decode entire trees of items:

extension Node: Codable where Value: Codable { } 

I don’t know about you, but I will never cease to be amazed by conditional conformances in Swift.

Moving on, the second change I improvement to make is a way to know the total size of a tree, returning a single integer count of all items we have.

Making this work only really requires one line of code, but it’s a recursive line: this code will call itself, which allows us to traverse the entire tree.

If our root node has two children, then the total size of the tree is 3: one for the root node, plus the count of the children. If both of those children have two children, then we have one for the root node, plus one for each of the root children, plus the count of the grandchildren, making 7 in total.

Expressed in a more general way, the count for any part of the tree is equal to 1 plus the count property of each of its children. This is what makes our code recursive: fetching the size of a child node means counting its children, which will count its grandchildren, and so forth.

Swift actually lets us sum this up in a beautifully simple way – add this property to the Node struct node:

var count: Int {
    1 + children.reduce(0) { $0 + $1.count }
}

To be clear, there is a big difference between $1.children.count and $1.count: the former will return how many nodes are inside the children array, whereas the latter will use our custom count property to recurse through all the children, grandchildren, and so on.

And boom, that’s it – we can now get an accurate count for any part of our tree. So, this will print 6, 2, then 3:

print(root.count)
print(andrew.count)
print(paul.count)

Our final improvement is to add a way to find a node inside our tree, so that we can say “give me the node with the value Paul,” and get it back if it exists. Once we have that we can read its children, grandchildren, etc, or just pull it out as a tree in its own right.

Just like reading the size of our tree, this needs to be recursive so that we can keep digging through all levels of our tree, but it also needs to be constrained so that we have a way of actually checking that a particular node value is the one we’re looking for.

Right now, our Node struct is generic over any kind of value, and we don’t want to change that. Instead, we’re going to make an extension constrained to Equatable values, allowing us to check whether the current node, or any of its children, match a particular value.

Remember, this needs to be recursive, which means we’ll look through all the children in our array and call find() on each of them. As soon as one returns a node we’ll send it back, but if we get through all of them without a match then we’ll send back nil instead.

Here’s that in code:

extension Node where Value: Equatable {
    func find(_ value: Value) -> Node? {
        if self.value == value {
            return self
        }

        for child in children {
            if let match = child.find(value) {
                return match
            }
        }

        return nil
    }
}

Now we can write code to find a particular node, and print out how many child nodes it has:

if let paul = root.find("Paul") {
    print(paul.count)
}

Classes vs structs

Before we move on, there’s one interesting behavior I want to mention because it might hit you by accident.

Earlier we modeled part of my family tree, including me and my two kids:

var paul = Node("Paul")
let sophie = Node("Sophie")
let charlotte = Node("Charlotte")

paul.add(child: sophie)
paul.add(child: charlotte)

If in the future Sophie had a child, we might model that like so:

var paul = Node("Paul")
Var sophie = Node("Sophie")
let charlotte = Node("Charlotte")

paul.add(child: sophie)
paul.add(child: charlotte)

let taylor = Node("Taylor")
sophie.add(child: taylor)

Note: You’ll need to change Sophie from let to var so we can modify her after creation.

The problem is that our Node type is a struct rather than a class, so we’ve created some inconsistency here: when Sophie was added to my list of children I got a unique copy of her node, and when later we added Taylor to Sophie’s children that didn’t affect my data – my copy of Sophie will still have no children.

So, printing paul.count will still print 3: myself, plus my two daughters. On the other hand, if we had moved the two new lines before the calls to paul.add(child:) then we would get 4, because my copy of the Sophie node would include Taylor too.

This is a direct side effect of us using structs, because each copy of the struct is unique rather than shared. If you want to change this then you should make Node into a final class instead, but a side effect of that is needing to implement Equatable and Hashable by hand.

This doesn’t take a great deal of work, so let’s try it out in case you were curious.

First, change struct Node to this:

final class Node {

Second, drop the mutating keyword from the add(child:) method, because that is no longer needed:

func add(child: Node) {

And now add custom conformances for both Equatable and Hashable, using both properties from our class:

extension Node: Equatable where Value: Equatable {
    static func ==(lhs: Node, rhs: Node) -> Bool {
        lhs.value == rhs.value && lhs.children == rhs.children
    }
}

extension Node: Hashable where Value: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(value)
        hasher.combine(children)
    }
}

Personally I’m not a big fan of this change. Yes, it means you can adjust any part of your tree in place and you won’t have to worry about the order in which you add children, but it can also create havoc if you pull out a subtree – you might expect that you can modify that subtree separately from the original tree, but changing one will in fact change both.

Try out both and see which you prefer!

Adding some sparkle

At this point our tree type is complete, either as a struct or as a class, and we can compare nodes, hash them, encode and decode them, and even search for specific values.

This all works great, but we can do better. You see, making trees is quite annoying: there are lots of nodes being created, and lots of calls to add(child:) too. Plus, if you’re using structs rather than classes, the order in which you create things matters even though it isn’t immediately obvious.

We can significantly improve the whole way we create trees in just a handful of lines of code thanks to function builders: a Swift 5.1 feature that lets us convert several components into a single value.

Function builders are huge, powerful, and complex things, but here we just need the tiniest of function builders to make some real magic happen. Like I said, function builders are designed to convert several values – in our case tree nodes – into a single value – in our case an array of tree nodes, because that’s matches the children array we have in our type.

One of the helpful features of function builders is that you only need to implement functionality for the parts you care about. In this case we don’t need to worry about conditions, loops, or other language features, but instead just one thing: if we’re given a variadic array of nodes, we need to convert that into a regular array of nodes that can be used for node children.

As you know, variadic parameters in Swift are automatically converted into arrays of those values, so our method can just send back the parameter directly.

Here’s how that looks in code:

@functionBuilder
struct NodeBuilder {
    static func buildBlock<Value>(_ children: Node<Value>...) -> [Node<Value>] {
        children
    }
}

Note: If you’re using any version of Swift before the final release of Swift 5.3, you must place an underscore after the @ sign, like this: @_functionBuilder.

That’s literally our entire function builder written, so we can start using that immediately by adding a third initializer to Node that accepts a value plus a NodeBuilder function that returns its children when called:

init(_ value: Value, @NodeBuilder builder: () -> [Node]) {
    self.value = value
    self.children = builder()
}

That’s our Node type fully upgraded, and it completely redefines the way we can make trees. Sure, we can still use the old manual approach if you want, but now we can use SwiftUI-like function builders that are much more natural:

let terry = Node("Terry") {
    Node("Paul") {
        Node("Sophie")
        Node("Lottie")
    }

    Node("Andrew") {
        Node("John")
    }
}

This way there’s no ambiguity about which child belongs where, or which order you should create things, because they are placed directly inside their parents.

Although function builders aren’t to everyone’s tastes, it’s great to have it as an option here – use them if you prefer them, or take the manual approach instead.

Further reading

If you’re curious how function builders work, Brent Royal-Gordon wrote a function builder designed to help you understand what the compiler is doing when it works with all possible function builder calls. I forked it on GitHub so the URL is permanent: https://gist.github.com/twostraws/f100939331eb87122149af7178ddde1a

Challenges

If you’d like to take this tutorial further, here are some suggestions:

  1. Implement the Comparable protocol for Node. Note: tree nodes that are comparable don’t need to compare their child arrays because that wouldn’t make sense.
  2. Add a new property called parent that lets children weakly store a reference to their parent. What impact does this have on the class vs struct question?

If you liked this, you'd love Hacking with Swift+…

Here's just a sample of the other tutorials, with each one coming as an article to read and as a 4K Ultra HD video.

Find out more and subscribe here


Using memoization to speed up slow functions

36:18

HIGH-PERFORMANCE APPS

FREE: Using memoization to speed up slow functions

In this article you’ll learn how memoization can dramatically boost the performance of slow functions, and how easy Swift makes it thanks to its generics and closures.

Creating a WaveView to draw smooth waveforms

32:08

CUSTOM SWIFTUI COMPONENTS

FREE: Creating a WaveView to draw smooth waveforms

In this article I’m going to walk you through building a WaveView with SwiftUI, allowing us to create beautiful waveform-like effects to bring your user interface to life.

How to use phantom types in Swift

24:11

ADVANCED SWIFT

FREE: How to use phantom types in Swift

Phantom types are a powerful way to give the Swift compiler extra information about our code so that it can stop us from making mistakes. In this article I’m going to explain how they work and why you’d want them, as well as providing lots of hands-on examples you can try.

Customizing ProgressView using ProgressViewStyle

15:06

INTERMEDIATE SWIFTUI

Customizing ProgressView using ProgressViewStyle

SwiftUI’s ProgressView gives us control over showing determinate or indeterminate progress, but it’s a bit dull – just a thin line and an activity spinner. Fortunately, we also get the ProgressViewStyle protocol so we can build entirely custom progress views, and in this article I’ll show you how it’s done.

User-friendly network access

14:26

NETWORKING

User-friendly network access

Anyone can write Swift code to fetch network data, but much harder is knowing how to write code to do it respectfully. In this article we’ll look at building a considerate network stack, taking into account the user’s connection, preferences, and more.

Controlling views using the accelerometer

39:03

SWIFTUI SPECIAL EFFECTS

Controlling views using the accelerometer

Reading device motion and orientation is a fast and slightly magical way to incorporate the real world into your apps, and can do a huge amount to add a little spark of delight to your UI. In this article I’m going to show you how easy it is to control SwiftUI layouts using the accelerometer, and give you a few ideas for special effects.

Creating an AccessibleStack that flips stack axis based on Dynamic Type

11:12

CUSTOM SWIFTUI COMPONENTS

Creating an AccessibleStack that flips stack axis based on Dynamic Type

There are several times when you might want to flip between a HStack and VStack, but one useful option is to look at the Dynamic Type size. Apple uses this itself to switch list rows to a vertical layout when using larger fonts, and in this tutorial I’ll show you how it’s done.

Using dates safely and effectively

18:36

MAKING THE MOST OF FOUNDATION

Using dates safely and effectively

Working with dates in software is hard, and if you don’t understand why then think about time zones, think about leap years, or think about how it’s the year 2563 in the Thai calendar. Apple gives us many tools for making them easier but they can be hard to discover, so in this article I’m going to try to provide some clear guidance for what to use and when.

The ultimate Box type

13:45

INTERMEDIATE SWIFT

The ultimate Box type

Boxing allows us to wrap up a struct in a class, to make it easy to share in several places. I’ve touched on boxing briefly previously, but here I want to take the concept much further to add useful protocol conformances that really powerful up its usefulness.

Creating a FilteringList to filter a list using text input

27:34

CUSTOM SWIFTUI COMPONENTS

Creating a FilteringList to filter a list using text input

Many apps show lots of data in a list, and allow users to filter that list by typing in a text view. In this article we’re going to build that in SwiftUI, then pull it out into a reusable component you can apply anywhere.

Understanding generics – part 2

30:48

INTERMEDIATE SWIFT

Understanding generics – part 2

In this second tutorial on generics, we’re going to explore creating several different generic types, look at extending generics, and look at how we can apply our generics knowledge to create property wrappers.

Codable networking with Combine

16:18

NETWORKING

Codable networking with Combine

So much of our job is about downloading JSON data, decoding it using Codable, then presenting it – it’s a core skill. But it’s common to see folks rely on huge libraries such as Alamofire, or get mixed up with URLSession. So, in this article we’ll look at how to rewrite common networking code using Combine, then add some generics to make it truly flexible.

Building a RadialMenu that shows many buttons around it

32:13

CUSTOM SWIFTUI COMPONENTS

Building a RadialMenu that shows many buttons around it

Sometimes pressing a button needs to present more buttons, and although you can use an action sheet for this it’s not ideal because it appears in a different location. In this article I’ll show you how to build a radial menu, which solves the problem by presenting a ring of buttons close to the user’s touch.

Removing optionals from your code

31:24

INTERMEDIATE SWIFT

Removing optionals from your code

Optionals are one of Swift’s most powerful features, letting us write code that is guaranteed to be safe as long as we check and unwrap them carefully. However, more often than not I prefer to avoid optionals as often as possible, and in this article I’ll outline some approaches for doing so.

Uploading Codable data

27:13

NETWORKING

Uploading Codable data

In a previous article we already looked at a great way to download data using Combine, but in this article we’re going to examine the other side of the problem: uploading Codable data. Apple’s API here is a little gnarly, so I’m going to show you how to wrap it in a neat container using generics and Result.

Creating a FlipView to provide a card flip effect

14:11

CUSTOM SWIFTUI COMPONENTS

Creating a FlipView to provide a card flip effect

If you’re looking for a simple and fun special effect to add to your code, I’ve got just the thing for you. In this article I’m going to walk you through building a FlipView with SwiftUI, which will encapsulate how to move between a front view and a back view using a 3D flip animation.

Handling names correctly

18:50

MAKING THE MOST OF FOUNDATION

Handling names correctly

There are lots of UI mistakes we can make in programming, but unless our bugs actually get in the way of functionality most users don’t care that much. But there is one exception, and we’re going to look at it here: in this article I’ll show you how to handle names correctly – the most personal data of all.

Creating chained network requests with Combine

18:36

NETWORKING

Creating chained network requests with Combine

We already looked at how to fetch decodable data using Combine, and also how to fetch and merge multiple sources of data. In this article we’ll tackle something even more complex: creating chained network requests, where the information retrieved from one request must be used to create multiple other requests.

Customizing Toggle using ToggleStyle

9:28

INTERMEDIATE SWIFTUI

Customizing Toggle using ToggleStyle

Most of the time the built-in iOS controls are great, but sometimes you want something just a little different. In this article I’m going to walk you through how you can take complete control over the way toggle switches work in SwiftUI, providing custom rendering and interactions.

Creating a custom property wrapper using DynamicProperty

14:20

INTERMEDIATE SWIFTUI

Creating a custom property wrapper using DynamicProperty

It’s not hard to make a basic property wrapper, but if you want one that automatically updates the body property like @State you need to do some extra work. In this article I’ll show you exactly how it’s done, as we build a property wrapper capable of reading and writing documents from our app’s container.

Link copied to your pasteboard.