Chapters

Hide chapters

Data Structures & Algorithms in Swift

Third Edition · iOS 13 · Swift 5.1 · Xcode 11

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

11. Tree Challenges
Written by Kelvin Lau

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now