11
Tree Challenges
Written by Kelvin Lau
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as
text.You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.
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...
}