## Data Structures & Algorithms in Swift

1 min

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

# 10. Trees Written by Kelvin Lau

The tree is a data structure of profound importance. It is used in numerous facets of software development, such as:

• Representing hierarchical relationships.
• Managing sorted data.
• Facilitating fast lookup operations.

There are many types of trees, and they come in various shapes and sizes. In this chapter, you will learn the basics of using and implementing a tree.

## Terminology

Many terms are associated with trees, and here are some you should know right off the bat.

#### Parent and child

Trees are viewed starting from the top and branching towards the bottom, just like a real tree, only upside-down.

#### Root

The topmost node in the tree is called the root of the tree. It is the only node that has no parent:

#### Leaf

A node is a leaf if it has no children:

## Implementation

Open up the starter playground for this chapter to get started. A tree consists of nodes, so your first task is to create a `TreeNode` class.

``````public class TreeNode<T> {
public var value: T
public var children: [TreeNode] = []

public init(_ value: T) {
self.value = value
}
}
``````
``````public func add(_ child: TreeNode) {
children.append(child)
}
``````
``````example(of: "creating a tree") {
let beverages = TreeNode("Beverages")

let hot = TreeNode("Hot")
let cold = TreeNode("Cold")

}
``````

## Traversal algorithms

Iterating through linear collections such as arrays or linked lists is straightforward. Linear collections have a clear start and end:

### Depth-first traversal

Write the following at the bottom of TreeNode.swift:

``````extension TreeNode {
public func forEachDepthFirst(visit: (TreeNode) -> Void) {
visit(self)
children.forEach {
\$0.forEachDepthFirst(visit: visit)
}
}
}
``````
``````func makeBeverageTree() -> TreeNode<String> {
let tree = TreeNode("Beverages")

let hot = TreeNode("hot")
let cold = TreeNode("cold")

let tea = TreeNode("tea")
let coffee = TreeNode("coffee")
let chocolate = TreeNode("cocoa")

let blackTea = TreeNode("black")
let greenTea = TreeNode("green")
let chaiTea = TreeNode("chai")

let soda = TreeNode("soda")
let milk = TreeNode("milk")

let gingerAle = TreeNode("ginger ale")
let bitterLemon = TreeNode("bitter lemon")

return tree
}
``````

``````example(of: "depth-first traversal") {
let tree = makeBeverageTree()
tree.forEachDepthFirst { print(\$0.value) }
}
``````
``````---Example of: depth-first traversal---
Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk
``````

### Level-order traversal

Write the following at the bottom of TreeNode.swift:

``````extension TreeNode {
public func forEachLevelOrder(visit: (TreeNode) -> Void) {
visit(self)
var queue = Queue<TreeNode>()
children.forEach { queue.enqueue(\$0) }
while let node = queue.dequeue() {
visit(node)
node.children.forEach { queue.enqueue(\$0) }
}
}
}
``````

``````example(of: "level-order traversal") {
let tree = makeBeverageTree()
tree.forEachLevelOrder { print(\$0.value) }
}
``````
``````---Example of: level-order traversal---
Beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon
``````

### Search

You already have a method that iterates through all the nodes, so building a search algorithm shouldn’t take long. Write the following at the bottom of TreeNode.swift:

``````extension TreeNode where T: Equatable {
public func search(_ value: T) -> TreeNode? {
var result: TreeNode?
forEachLevelOrder { node in
if node.value == value {
result = node
}
}
return result
}
}
``````
``````example(of: "searching for a node") {
// tree from the last example

if let searchResult1 = tree.search("ginger ale") {
print("Found node: \(searchResult1.value)")
}
if let searchResult2 = tree.search("WKD Blue") {
print(searchResult2.value)
} else {
print("Couldn't find WKD Blue")
}
}
``````
``````---Example of: searching for a node---
Found node: ginger ale
Couldn't find WKD Blue
``````

## Key points

• Trees share similarities to linked lists, but a tree node can link to many child nodes where linked-list nodes may only link to one successor node.
• Every tree node, except for the root node, has exactly one parent node.
• A root node has no parent nodes.
• Leaf nodes have no child nodes.
• Be comfortable with the tree terminology such as parent, child, leaf and root. Many of these terms are common tongue for fellow programmers and will help explain other tree structures.
• Traversals, such as depth-first and level-order traversals, aren’t specific to the general tree. They work on other kinds of trees, although their implementation will be slightly different based on how the tree is structured.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.