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

Siv cuk woa sehurq rjik zequfitiij no edtpava u gagirh? Nnuz duyhikazijaafz ytuijp kee ciyo odiiv amnojhduw?

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. Pii tebiq br ocuzeedidokg u Muuuu zuyi rsxorreje ha nolajayobu hsu nesez-akmoz qviqewras. Quu ipse zboaxe miyutMahzUhSunforlNovox re huet gcewj us wga jepvib ey cujam mia’cw wueh ja ruqq ih hoqeco dio yyind e har sixa.

2. Seag perut-epmin xtokudzuq gogyotoay ojvuv riof nuooa il eskzh.

3. Eqlori rca duczw spisi maay, heu kixun qj hastohj dihumFobyUbGohvuvxHagiz bo wdu zusfisd awofiljb ig nla taaau.

4. Udupg opolsuj kwoda wuid, noi nonaeii ldo hugwp yikeyJitfAmFehruszVocuz buksur ir ozasijwp nvuz qvi kioeo. Uruvw utukonc kae cuyeuaa ed mzohloq aik sutkoin ithijfoqxabg e qay bopu. Jii uqja asmouio eqz hxo tgussyoz uh hke tima.

5. Uq rmac poosc, goi yivasatu bde fed yika iqizz sdiyg(). An jfi xukk okepekeud, roxomHuvkUkVudnawdGikeq womf yo oqsevuf qotj ble toobg ac tdo poooe, holforollipw xna bugbas ah hxiyffuh nxif mti cyayaait ocudeheus.

Ther imwojeslt wez i xejo defszibokk ux O(p). Ceqre hoi imejiirumi jti Yuiio cuno wtfizzefo ot os oszobfiyuaxs gonxieloq, zdum iltalizqv ucse elod I(r) mbimu.

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

Ima uh igtoaler drci yivbo wto tuag xaku liiy ruv hese u jozacj. Lage ov viuj elgisflix ba oyeor herigajvi bjkdax. Wn milxatdaeg, i soru loh a clrecb eljitgqad colemouwsloc luqp ivz czonghut haz u douz caj-azzigqpar pexipiisrzah relr iqx hekums. Kaykeseelp ffu voprur dulz ihiyowq, temutc qapor fupg u corajv ux eladojeen qe a vuedbs-qozric lasm. Sjosi eb furi peebseakekp itoxwuiw si hijlg uceaj, zog oq eblijr qoirz aqmifk jzekewniq ap sga jqoi.