Swift Tree, Binary Tree With Examples [Latest]

Swift Trees

Trees are a data structure that is just opposite to the real-life tree. The topmost node is called the root.

Trees are a non-linear data structure, unlike Arrays. Trees structure have a hierarchy.

A node is a structure that holds data and also references to its child nodes.

Root is the topmost node of the tree.

A node that doesn’t have any children is known as a leaf.

Trees are useful in sorting data, efficient searching, implementing routing table etc.

A diagram of a Tree is illustrated below:

The red box is the root node. The black boxes are nodes. The green boxes are the leaf of the tree.

Let’s create a Tree data structure using Swift.

Launch XCode playground and start rolling!

Creating Swift Tree

The following swift class contains the code for the Node of a tree.

class Node<T>{
    var data: T
    var children: [Node] = []
    weak var parent: Node?
    init(_ data: T) {
        self.data = data
    }
}

In the above code, we’ve set the data of the node in the init method.

A Node can have any number of children. We’ve created an Array to add child nodes to the current node.

Besides, we can set the reference to parent node as well. For this, we’ve set the reference to weak var to prevent strong cycles which can cause memory leaks.

Let’s instantiate the tree and add children.

let root = Node<Any>("Root")
let aNode = Node<Any>(1)
let bNode = Node<Any>(2)
let cNode = Node<Any>(3)
let dNode = Node<Any>("Anupam")
let eNode = Node<Any>("Swift")
root.children = [aNode, bNode, cNode]
aNode.children = [dNode,cNode]
bNode.children = [dNode,eNode]
eNode.children = [Node("x"),Node("y"),Node(100)]

We’ve created a Generic type Tree, hence you need to state the type when defining.

So far so good. Next, how to print the tree?

Recursion is an important part of most operations on the data structure trees. Recursion is the key since every node is similar in structure – they either have children or they don’t.

Hence, to perform any operation you need to invoke the method on the node’s children. The trivial condition would be when there’s just a single node (root node). That’s where you do the operation.

Add the following function in the class Node

func printNodeData() -> [String] {
        return ["(self.data)"] + self.children.flatMap{$0.printNodeData()}.map{"    "+$0}
    }
    func printTree() {
        let text = printNodeData().joined(separator: "n")
        print(text)
    }

In this we need to convert the data to a string since the type is generic. So we enclose it in "()".

Adding and Searching in a Tree

In the above code, we’ve added nodes to the parent in a hardcoded way. Let’s create a function for it.

Furthermore, let’s create a function for searching an element in the tree.

Add the following functions in the node class.

func addNode(child: Node)
    {
        children.append(child)
        child.parent = self
    }
    func search(element: T) -> Node?
    {
        if "(element)" == "(self.data)"{
            return self
        }
        for child in children{
            if let result = child.search(element: element){
                return result
            }
        }
        return nil
    }

Let’s build a small tree and print it in the console.

Types of Trees

Following are the different kinds of trees:

• Binary Tree
• AVL Tree
• Binary Search Tree
• B-Tree
• Minimum Spanning Tree
• Radix Tree
• Red-Black Tree
• Segment Tree
• Threaded Binary Tree
• Tries
• Union-Find

We’ll cover each of these later. In the next section, we’ll be discussing Binary Trees.

Binary Trees

Binary trees are data structures in which a node can have only 0, 1 or 2 children.

The following class is used to create a Binary Tree.

class TreeNode {
    var value: Int
    var leftChild: TreeNode?
    var rightChild: TreeNode?
    init(_ value: Int,_ leftChild: TreeNode?,_ rightChild: TreeNode?) {
        self.value = value
        self.rightChild = rightChild
        self.leftChild = leftChild
    }
}

Let’s build it by adding nodes and child nodes.

let ten = TreeNode(10,nil,nil)
let one = TreeNode(0,nil,nil)
let third = TreeNode(3,nil,nil)
let fourth = TreeNode(4,nil,nil)
let five = TreeNode(5,ten,third)
let six = TreeNode(6,fourth,nil)
let root = TreeNode(2,five,six)

Following is how the tree looks like:

Height of Binary tree

The depth of a node is the number of edges from the node to the tree’s root node.
A root node will have a depth of 0.

The height of a node is the number of edges on the longest path from the node to a leaf.
A leaf node will have a height of 0.

Height of a tree begins at the root node and is equal to the depth of the farthest leaf. The leaf with the longest path.

Add the following function in the TreeNode class.

func maxDepth(_ root: TreeNode?) -> Int{
        if root == nil{
            return 0
        }
        else{
            let lDepth = maxDepth(root?.leftChild);
            let rDepth = maxDepth(root?.rightChild);
            if (lDepth > rDepth){
                return(lDepth+1)
            }
            else {
                return(rDepth+1)
            }
        }
    }

To get the height of the tree, invoke the function on an instance of TreeNode and pass the root.

let t = TreeNode(0,nil,nil)
t.maxDepth(root) //3

Binary Tree Tranversals

We can traverse the tree in three possible ways:

1. Inorder – Prints the left child value then current node value and lastly right child value.
2. Postorder – Prints left and right child values then current node value.
3. Preorder – Prints current node value followed by left and right child values.

Let’s write a function for each of them in the TreeNode class.

func inorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }
        var result: [Int] = []
        result += inorderTraversal(root!.leftChild)
        result.append(root!.value)
        result += inorderTraversal(root!.rightChild)
        return result
    }

We recursively call the leftmost subtree followed by printing the node value and then calling the rightmost subtree.

Preorder:

func preorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }
        var result: [Int] = []
        result.append(root!.value)
        result += preorderTraversal(root!.leftChild)
        result += preorderTraversal(root!.rightChild)
        return result
    }

Postorder:

func postorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }
        var result: [Int] = []
        result += postorderTraversal(root!.leftChild)
        result += postorderTraversal(root!.rightChild)
        result.append(root!.value)
        return result
    }

The output is given below:

This brings an end to this tutorial on Trees and Binary Trees in Swift.