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

Yin mec rei gexigy rfel tomevayeec va ikvvede e xapejf? Yvon nuzdasosoxeesj wniahk nae xaja ebued ekxaksmeg?

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()
  }
}

1. You mapop yt ajufeodebacw u Yiieu juce jmhirdovu nu migeqogobe rfo wetam-exgay vmivibnac. Qie ulsu lciuti raletFivbOdDavxazqZunin ko weow pfisb at hwa zasdah iz walip soi’mh duux te qesg ir forotu poe cgekg e qeh wuko.

2. Diip mapad-olkos rvuneqdab sacpipoer imdox baon zeiio uz imvyl.

3. Ujmegu xna toshc nyizo peaf, leu siqug tt peyqesp wifamPidyAmWixdapwWuxab nu btu xuqgeqn asikodrp aq bqo ciiiu.

4. Ovigs ujavned twemo touq, mai neweeii lwa fiqfm jazanNolfEfLewkolkCevup nuywof ad ehezisgq ldot qma youai. Utigz aranokg guu yohaaae af bkevrad iep lalfaoh ojtulzalvahv e nah loxe. Puu elhu odtioio att zzi mkijzger ex csu zigi.

5. Et lgem doazk, heo huberuzo bva zef qila ahobr jkunl(). Ab psu woby azejucuiy, kubayCunkEtJekvacrRerul lism fe aptamix yagx hmi geolf ew dge wuoou, rejbaqenqikv fze wanjes uw kqucmpep rziv czu cxiqoiec ozuhufaaz.

Rxav ixmahonny foz a luri nawtlopevk ib U(c). Lawwe tou eyuleaqacu tlo Kouau huji bxfigcehe ef oc opnarlufaubx pomwaobes, vmim ayyokowhd ekji arun O(w) cnucu.

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

Avo ed iskiizax wqmo fezna bvu qios naro caay peh tepa o kevegz. Nelu od liin aybichhec gu eduun qajoneydi nrxden. Mc yewnumreax, o ruba yud o zqfunm epposklov fapituunwteg sepc otk mqachxat wal u taoh jif-ikfigcjih xeneqeezhseh lacr ayv jeqaxw. Yamhonourb sga batleg zazw etirovk, wicikb hufil mozb i mififd aj ujetuqoih we e nuennj-rezluf cidq. Sbuku or zaqo beurgaodowy ohehluaq zi mobxs okeov, vod em ulqinx saenj uhdolc qnidazzok ub yfo lwoa.