In this tutorial, we’ll be discussing the Data Structure Trees and implement it using Swift. Furthermore, we’ll see what are Binary Trees and implement a few of its well-known algorithms.

Table of Contents

## 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.

**Degree**: is the total number of children in a node.**Siblings**: Nodes that have the same parent.**Edge**: A Connection between two nodes.

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.

```
Copy
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.

```
Copy
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`

```
Copy
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.

```
Copy
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.

```
Copy
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.

```
Copy
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.

```
Copy
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.

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

### Binary Tree Tranversals

We can traverse the tree in three possible ways:

**Inorder**– Prints the left child value then current node value and lastly right child value.**Postorder**– Prints left and right child values then current node value.**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.

```
Copy
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**:

```
Copy
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**:

```
Copy
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
}
```

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

Deepika says

September 11, 2018 at 8:40 pmI think there is a copy paste error for preorderTraversal and postOrderTraversal code.

‘result += inorderTraversal(root!.leftChild) ‘ in preorderTraversal method should be actually

result += preorderTraversal(root!.leftChild) and similar in postOrderTraversal

Anupam Chugh says

September 12, 2018 at 10:38 pmThanks Deepika.

Fixed it.

ranin sofyan says

July 14, 2018 at 8:20 amhow to learn the binary tree?

Anupam Chugh says

July 30, 2018 at 1:25 pmThis tutorial explains binary tree with implementation.