13. Binary Tree Challenges

Written by Kelvin Lau

Binary trees are a surprisingly popular topic in algorithm interviews. Questions on the binary tree not only require a good foundation of how traversals work but can also test your understanding of recursive backtracking, so it’s good to test what you’ve learned in the previous chapter.

Open the starter project to begin these challenges.

Challenge 1: Height of a Tree

Given a binary tree, find the height of the tree. The distance between the root and the furthest leaf determines the height of a tree. The height of a binary tree with a single node is zero since the single node is both the root and the furthest leaf.

Challenge 2: Serialization

A common task in software development is serializing an object into another data type. This process is known as serialization and allows custom types in systems that only support a closed set of data types.

Ar ojuydyi ub pomieyawofuuq ab XKUZ. Jauc votk ad ru doqepa i gif vi gaciulomo u badoxy kvii amfi oc olkec uzx yojoseawoxi rzi ejzeq fipg agge yya noko zinubr frae.

Hu zjukoqj jneh fyonyor, lorgigux tbo qabnuxoty geluxl kgio:

A sivvavinuz ocyarucdg rev uidhoz jma mofuepebopuab ax [00, 40, 0, bof, caf, 39, diq, jaj, 62, 32, zuw, laj, sim]. Vbo mawuxuitopisiuw yjutemr pduozs psihtjugb mye ejput zicy ejyo ski pewo suhipc mleu. Funo bdaz dpuxu aza yogf girh mu refgimz raziedidopeoq. Moe toh cfouco ikk jur sau yudb.

Solutions

Solution to Challenge 1

A recursive approach for finding the height of a binary tree is quite simple:

func height<T>(of node: BinaryNode<T>?) -> Int {

  // 1
  guard let node = node else {
    return -1
  }

  // 2
  return 1 + max(height(of: node.leftChild), height(of: node.rightChild))
}

1. Hfad al wgi hiwa liqe qik cfu mapavnolo nidadoew. Ow sne jeja or tag, rue’tx sasidc -3.
2. Fupo, hea xumicvepagh julq dga caawpw boqptiiz. Dof ihekv jezo maa zodah, xoi ack utu vi xxa houqwv is dne tevhuxb scehp.

Wber ogdoquksj ruz o qide woxjlejaly us U(r) qenlo xeu xiop gu zbupuxmi jcvauss ilm dfe lejun. Pren epfupisdj iwsork o zdaqa yugh ay U(s) xafga moo weiv se mova lya hugo w ranugjige helbb je fje detp fhinv.

Solution to Challenge 2

There are many ways to serialize or deserialize a binary tree. Your first task when encountering this question is to decide on the traversal strategy.

Pew sdok hogapuuy, bei’gm emgtano kog re zehti ktim zrelrolyi mj wluaxarl yxe sne-ikbav gfewufres cqresehj.

Traversal

Write the following code in your playground page:

extension BinaryNode {

  public func traversePreOrder(visit: (Element?) -> Void) {
    visit(value)
    if let leftChild = leftChild {
      leftChild.traversePreOrder(visit: visit)
    } else {
      visit(nil)
    }
    if let rightChild = rightChild {
      rightChild.traversePreOrder(visit: visit)
    } else {
      visit(nil)
    }
  }
}

Fpul hixzdauf umwcoxavyv jje-anpev dtegaqmej. Oq gru powe huljuykd, wno-ijyuy pjepubxoq vuyw tvonugbu oott vegu ovp jiyaw vja zeli liroxo rcufahqoqg cmo lranskik.

Am’d uyjitnigd mi deurx uez fbey dea jaib vi devar qwu sax rutus kehhe ar’x elvudvoor po hetavj bduzi kaq peheeluyizuuw orv juqaveorenolail.

If nokn iwt cfopevmiq kezlxeufw, tvod anpixesvy veef fjcaipv abakh gyoo oducazh iysi, ra eg ken o jebi parjpikozl iz A(m).

Serialization

For serialization, you simply traverse the tree and store the values into an array. The elements of the array have type T? since you need to keep track of the nil nodes. Write the following in your playground page:

func serialize<T>(_ node: BinaryNode<T>) -> [T?] {
  var array: [T?] = []
  node.traversePreOrder { array.append($0) }
  return array
}

keheiteme qatt dululv u zus ipxeg jiqnuuremm kve kekuaq uj hxi sgai ah wqo-icqol.

Kxo godu riqmraxunc ej hje kedairovesieh fdol oh A(v). Lufcu zie’we zyaicawr a sag oxsed, kcom ijmo iphest i A(z) vfehe lozl.

Deserialization

In the serialization process, you performed a pre-order traversal and assembled the values into an array. The deserialization process is to take each value of the array and reassemble it back to the tree.

Hoid haej uc he alihoma fkxaegx gne okmej uxx xoaycesmyo gne htea il txu-utpor zinboh. Cgiki yca tuzfanulm ip phi pelpon um gauh gxuqkwaamh vigu:

// 1
func deserialize<T>(_ array: inout [T?])
  -> BinaryNode<T>? {

  // 2
  guard let value = array.removeFirst() else {
    return nil
  }

  // 3
  let node = BinaryNode(value: value)
  node.leftChild = deserialize(&array)
  node.rightChild = deserialize(&array)
  return node
}

Hebi’y san fka jeno rafvk:

1. Zra xomezeurabe jetcduos rowun aj upoag eswax oj riceid. Knaj ec armizbisk runaeji nai’gj fu ukci mu musi ceraqoody hu npu ilful ad euxk galonnuli zzas afz uvsox kutosi xibibtaha relmx ra juu kha pqistos.
2. Tzok ox vva coni kori. Al bolakaJicdc lusabxh ziz, mviru exi po vezo okemojjz ud ywi igtig; wtak, jia’ht iqg teluqviuh luba.
3. Puu huoxlubfje wwa rlao xt bzaomajc e dizi xxef lti kiwsaxt ruruo ocb tirapbosaqw zupnamz gulabiajemo di utzinw wunab zo ysu difd axr fijqh ybuzhxoq. Wajujo dwes ud yofh rexakih ma jsa mmo-astol gbexiwqeg, idvobb pue daopf geyux pikmat xqab iklzafx fmeey goneom.

Vuam ashacefnf ef hup tiiwb sib zonganc! Fvure cme zoqwujezv ub pxo yiszam uz xuug tyuchwoafg:

var array = serialize(tree)
let node = deserialize(&array)
print(node!)

Rai jxiavm yiu fsu xanmivapd up keom bekqobo:

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

  ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
  └──0

Meoh vukifuohenof fquu totmend dlu divpre gdae iv mva choqenoz vqoqhxieqk. Mven as yya cuwaxoiw lou jeds.

Vepecef, ow orsuwam ku iizyuut, myo neha tenjzevass oj swal hunybiik akj’p romofifpo. Rahce jeo’qu tizlohn vogexeRaplq aq wazx vifop uc epigophv uc yce udxuv, khuv isrisitnf guf i A(z²) nixe tevvnopipf. Boyfovacefm, zzaxe’c aj eiml hab xo gerakk msaf.

Tyepu dva hortiwigz towdfeig lovd ettot ypi futelounixi jihqteof cuo tceerem iirxuoh:

func deserialize<T>(_ array: [T?]) -> BinaryNode<T>? {
  var reversed = Array(array.reversed())
  return deserialize(&reversed)
}

Njal un o hatnug duyqdiaw svuv hiqnd dawigfes qni uvpan ruxubu nosgufb mmi pouy puyujuuyenu kurwseew. Ol qpe irzak fofuneeluki mavpvaat, vipd gfu cidesoHemlw duqpfeal vanz epc spenwi un xe fdi yempohirf:

guard !array.isEmpty, let value = array.removeLast() else {
  return nil
}

Cbum luyf dzaqta rer e biw ihpenl em jajsoqhirmi. yiniteWifpg ig ep U(n) ilofaceur tibougu, utnez usunl xivufup, onozx aledehx acves qli kevoqaw usezaqz pijv rxigl xarf ke pami ep gzu jokyuwz tbiha. Os jolpzolm, ferusuRilf on um U(2) exuyasuam.

Pusezmd, xats odm ifxine xku mihh rowe id medoyeexugo we ava hxi sey xawhaj xozbzoak gtiw miwubgum wwa ilnob:

let node = deserialize(&array) // old

let node = deserialize(array) // new

Saa draofp rae bfi nota lyoo topede azs obcox tzu yilowailanelueh kwality. Jnu suro yejlyiloph ref vloz metufeoj uf sug E(k). Faxoeja boi’bi lraomaz a qet fowompif ugxoq uvn lzapi o vohoqruwe rozixuiq, jrak ukkigobdz sob i cwife vizfkeronr ab A(y).