## Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

# 11. Tree Challenges Written by Kelvin Lau

### Challenge 1: Print a tree in level order

Print all the values in a tree in an order based on their level. Nodes in the same level should be printed on the same line. For example, consider the following tree:

Your algorithm should print the following:

``````15
1 17 20
1 5 0 2 5 7
``````

Hint: Consider using a `Queue` included for you in the Sources folder of the starter playground.

### Challenge 2: Parents and ownership

Consider the original definition of a tree node:

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

public init(_ value: T) {
self.value = value
}
}
``````

## Solutions

### Solution to Challenge 1

A straightforward way to print the nodes in level-order is to leverage the level-order traversal using a `Queue` data structure. The tricky bit is determining when a newline should occur. Here’s the solution:

``````func printEachLevel<T>(for tree: TreeNode<T>) {
// 1
var queue = Queue<TreeNode<T>>()
var nodesLeftInCurrentLevel = 0
queue.enqueue(tree)

// 2
while !queue.isEmpty {

// 3
nodesLeftInCurrentLevel = queue.count

// 4
while nodesLeftInCurrentLevel > 0 {
guard let node = queue.dequeue() else { break }
print("\(node.value) ", terminator: "")
node.children.forEach { queue.enqueue(\$0) }
nodesLeftInCurrentLevel -= 1
}

// 5
print()
}
}
``````

### Solution to Challenge 2

You can add a property `parent` to the `TreeNode` like so:

``````public class TreeNode<T> {

public weak var parent: TreeNode?

// etc...
}
``````
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.