Building tree data structures in Swift

What’s a tree?

A tree is an summary knowledge construction that can be utilized to signify hierarchies. A tree normally accommodates nodes with related knowledge values. Every node can have baby nodes and these nodes are linked collectively through a parent-child relationship.

The identify tree comes from the real-world, each digital and the bodily bushes have branches, there’s normally one node that has many youngsters, and people can even have subsequent baby nodes. 🌳

Every node within the tree can have an related knowledge worth and a reference to the kid nodes.

The root object is the place the tree begins, it is the trunk of the tree. A department node is just a few a part of the tree that has one other branches and we name nodes with out additional branches as leaves.

After all there are numerous sorts of tree constructions, possibly the commonest one is the binary tree. Strolling by means of the gadgets in a tree is named traversal, there are a number of methods to step by means of the tree, in-order, pre-order, post-order and level-order. Extra about this in a while. 😅

Information bushes utilizing structs in Swift

After the short intro, I would like to indicate you the right way to construct a generic tree object using structs in Swift. We’ll create a easy struct that may maintain any worth sort, through the use of a generic placeholder. We’re additionally going to retailer the kid objects in an array that makes use of the very same node sort. First we will begin with a easy Node object that may retailer a String worth.

struct Node 
    var worth: String
    var youngsters: [Node]


var baby = Node(worth: "baby", youngsters: [])
var guardian = Node(worth: "guardian", youngsters: [child])

print(guardian) 

Let’s alter this code by introducing a generic variable as an alternative of utilizing a String sort. This fashion we’re going to have the ability to reuse the identical Node struct to retailer every kind of values of the identical sort. We’re additionally going to introduce a brand new init methodology to make the Node creation course of only a bit extra easy.

struct Node<Worth> 
    var worth: Worth
    var youngsters: [Node]
    
    init(_ worth: Worth, youngsters: [Node] = []) 
        self.worth = worth
        self.youngsters = youngsters
    


var baby = Node(2)
var guardian = Node(1, youngsters: [child])

print(guardian)

As you may see the underlying sort is an Int, Swift is sensible sufficient to determine this out, however you can even explicitly write Node(2) or in fact every other sort that you simply’d like to make use of.

One factor that you need to notice when utilizing structs is that these objects are worth varieties, so if you wish to modify a tree you will want a mutating operate and you need to watch out when defining nodes, you would possibly need to retailer them as variables as an alternative of constants if it’s essential alter them in a while. The order of your code additionally issues on this case, let me present you an instance. 🤔

struct Node<Worth> 
    var worth: Worth
    var youngsters: [Node]
    
    init(_ worth: Worth, youngsters: [Node] = []) 
        self.worth = worth
        self.youngsters = youngsters
    
    
    mutating func add(_ baby: Node) 
        youngsters.append(baby)
    


var a = Node("a")
var b = Node("b")
var c = Node("c")

a.add(b)

print(a)


b.add(c) 

print(a)


print(b)

We have tried so as to add a toddler node to the b object, however because the copy of b is already added to the a object, it will not have an effect on a in any respect. You need to watch out when working with structs, since you are going to cross round copies as an alternative of references. That is normally a fantastic benefit, however generally it will not provide the anticipated conduct.

Yet another factor to notice about structs is that you’re not allowed to make use of them as recursive values, so for instance if we might wish to construct a linked record utilizing a struct, we can’t have the ability to set the subsequent merchandise.

struct Node 
    let worth: String
    
    let subsequent: Node?

The reason of this subject is well-written here, it is all in regards to the required house when allocating the item. Please strive to determine the explanations by yourself, earlier than you click on on the hyperlink. 🤔

Easy methods to create a tree utilizing a Swift class?

Most common examples of tree constructions are utilizing courses as a base sort. This solves the recursion subject, however since we’re working with reference varieties, we’ve got to be extraordinarily cautious with reminiscence administration. For instance if we need to place a reference to the guardian object, we’ve got to declare it as a weak variable.

class Node<Worth> 
    var worth: Worth
    var youngsters: [Node]
    weak var guardian: Node?

    init(_ worth: Worth, youngsters: [Node] = []) 
        self.worth = worth
        self.youngsters = youngsters

        for baby in self.youngsters 
            baby.guardian = self
        
    

    func add(baby: Node) 
        baby.guardian = self
        youngsters.append(baby)
    


let a = Node("a")
let b = Node("b")

a.add(baby: b)

let c = Node("c", youngsters: [Node("d"), Node("e")])
a.add(baby: c)

print(a) 

This time once we alter a node within the tree, the unique tree shall be up to date as properly. Since we’re now working with a reference sort as an alternative of a price sort, we are able to safely construct a linked record or binary tree through the use of the very same sort inside our class.

class Node<Worth> 
    var worth: Worth
    
    var left: Node?
    var proper: Node?
    
    init(_ worth: Worth, left: Node? = nil, proper: Node? = nil) 
        self.worth = worth
        self.left = left
        self.proper = proper
    



let proper = Node(3)
let left = Node(2)
let tree = Node(1, left: left, proper: proper)
print(tree) 

After all you may nonetheless use protocols and structs should you want worth varieties over reference varieties, for instance you may give you a Node protocol after which two separate implementation to signify a department and a leaf. That is how a protocol oriented method can appear like.

protocol Node 
    var worth: Int  get 


struct Department: Node 
    var worth: Int
    var left: Node
    var proper: Node


struct Leaf: Node 
    var worth: Int



let tree = Department(worth: 1, left: Leaf(worth: 2), proper: Leaf(worth: 3))
print(tree)

I like this solution quite a bit, however in fact the precise alternative is yours and it ought to at all times rely in your present use case. Do not be afraid of courses, polymorphism would possibly saves you various time, however in fact there are circumstances when structs are merely a greater approach to do issues. 🤓

Implementing bushes utilizing Swift enums

One very last thing I would like to indicate you on this article is the right way to implement a tree utilizing the highly effective enum sort in Swift. Identical to the recursion subject with structs, enums are additionally problematic, however luckily there’s a workaround, so we are able to use enums that references itself by making use of the indirect keyword.

enum Node<Worth> 
    case root(worth: Worth)
    oblique case leaf(guardian: Node, worth: Worth)

    var worth: Worth 
        swap self 
        case .root(let worth):
            return worth
        case .leaf(_, let worth):
            return worth
        
    

let root = Node.root(worth: 1)
let leaf1 = Node.leaf(guardian: root, worth: 2)
let leaf2 = Node.leaf(guardian: leaf1, worth: 3)

An oblique enum case can reference the enum itself, so it’s going to allo us to create circumstances with the very same sort. This fashion we’re going to have the ability to retailer a guardian node or alternatively a left or proper node if we’re speaking a few binary tree. Enums are freaking highly effective in Swift.

enum Node<Worth> 
    case empty
    oblique case node(Worth, left: Node, proper: Node)


let a = Node.node(1, left: .empty, proper: .empty)
let b = Node.node(2, left: a, proper: .empty)
print(b)

These are only a few examples how one can construct numerous tree knowledge constructions in Swift. After all there’s much more to the story, however for now I simply wished to indicate you what are the professionals and cons of every method. It’s best to at all times select the choice that you simply like one of the best, there is no such thing as a silver bullet, however solely choices. I hope you loved this little publish. ☺️

If you wish to know extra about bushes, it’s best to learn the linked articles, since they’re actually well-written and it helped me rather a lot to grasp extra about these knowledge constructions. Traversing a tree can also be fairly an attention-grabbing matter, you may study rather a lot by implementing numerous traversal strategies. 👋