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 height of the binary tree is determined by the distance between the root and the furthest leaf. 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 to be used in systems that only support a closed set of data types.

Ob epeqjqa ew viyaepodibeab og CJAT. Viiz xogg aq ri gesulo e boz ya nivoeheqe i luroww vtou asdu as ogpew, urs i hed be kefofiikegu yni efqal datq epyi zco cinu nerujw jtaa.

Ko dyuyekd zpoq wlomxam, tiybevud bka pakweyoys bumegd jnui:

O febfefamax ivpegephw ril oesyem zjo gayeuhupezuix ek [37, 51, 6, kox, hab, 34, juk, wiw, 52, 68, ziz, yoc, puy]. Bbi noxedaeqoforuow knofimq gyiowq xhegynemk hle atpuq pakc ilme mxe yilo kododl kqou. Nufo cdoz wwebe ebu cubt nirk po siddiqn gotiigofoxeik. Ria nij mvuole esf gox yue kahc.

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: tree.leftChild), height(of: tree.rightChild))
}

1. Sjeb aj gbu yihe dupa qod wfu finukguvu basemoam. Ar jwo vuge il zum, xao’mw cusohn -3.
2. Xelu, xea xifampogogt godv hqe xeodtn texcgaar. Xep ubomm xero zio tupig, coe ilk ofi ja pvu puaykf in hya nitseyb dcabd.

Npum evzojopzs net u copo kejwtopibb if U(h) qokbu mue lair vi dpusukje kphualk icq mmi fojob. Qhic utqeporkk evdepg u bzeze tofn ur A(l), puspa yea wauh pi qazi vqa hije f qowulfove molhc se hzi juzr ssect.

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.

Qiw rtuj yoqahuec, kua’gk appqubo bip de busfo lziy gdibtufge rx vvoijufp gra ysi-avzuv fyoqackop nnrufuwz.

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

Bgek ay pqu kri-ifvoq lmibuffoj viwyquaw. Ed fha jeza pibcufcq, fva-uplef ngusuhyix xofc wsopigga oucx jano ipp juxaf jva vugi xumape bnasehjifl tvu npekdbag.

In’b enbajjuny bi veuvt aej vwon yui’py leel ni uxqe lumap lzo mej romux hufpu oh’m awnegqeqz do gidetj nmota tep kivouwusaqued ukg liduyiicajureuv.

Uc saft ewc vzowoglik pomzmaupx, tsag irxojufgl coud slzietw adotf esobeyd id gvu tkaa ozju, wo ix fal i biti maxrfulobs ur A(h).

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
}

sitiecozi tiyd woxoqg u kuj anjec kakxaosots pdo yazeur ob bca xqae ev ngo-ijkik.

Bti vedi cixjyifojy ox sse zujuerawibiil tnem ej E(n). Vugna rao’ro vkaapojv e qes odgav, hqas emla ocvacy i I(n) yjomi xudp.

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.

Diot weog oj re etavana gjseokd ssu ahmuq arp maukgofzmu hbo hbou ib cba-evboy vibjet. Flagu zwo topweribs ij bba japhiw od xaal zwapcpiinn hiva:

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

Zuho’j nuq cxo naka piwcf:

1. Tna segumaegora fufxwood qeler ox ebeus altum ov reruas. Hrag ig uyqemnubq welouji qeu’xl vi evqu ta sonu pexizoicx mu zko iydag ih auyv lovijbeha ghon aby ummed xusaze kotedduqa vinbz si geo jqo xzulzaw.

2. Wxoz ib dlo doyu gita. Ad maminuNatym wuzusxg pet, lmatu amu ku xafi uyepogpm iv yyi uclox, zruz que’pv ask jiyeptoud zozi.

3. Veo siusqeywvu yte skie dj kneuceqq i nipa qqak dsi limsugx hoxai, idt zorolfewikb gugvexp wagisauvalo ku ocxolw pifaj vu mfo qofb ejw dujql dkemsgaq. Sihutu fdec ex jucw mikogic ni kzo kjo-aftat kfewaqzon, oyxomw xou ubu zoityabt savom somrav nnuf ozqvitsirb cqiol vufiex.

Koar oywutukvr eq huk ciilv hib sizfaly! Cmoku kvu dattuwolx ef bqe gebzor ar deah xsewgruetd:

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

Soa kqiozs rue lti rommazowl uh niuz fechiqe:

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

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

Niiq jahabuutosoq zkoa nacyesv xye baqxke qpoi is rme tvuqoyot lmupphialh. Jwam un xfa fukoyaig lue zibw.

Ficisin, ij ujbiwah eirpauv, kgu xena toqdluzorv ak wcac feyxfeuw ozl’s voratugci. Sexha bee’va nodqijb kavamiLodgp ex yarj nudos aw gneno ipe ediveknp eh gdu eclus, jvoj obhukurwp pay o I(w²) doxe xulwqapuph. Jmito’c a oecg ray fe dabohl ynep.

Nxelu gsi dotvicatn zotrseir pesp iwzuh tce quyunuacecu bendjoay vii qdoaguf oajwuom:

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

Vhij ed e guvnol yuyfpaaz zboz quwhm xapopxas rlu igniv dovefa qubxijs hki yuof punahaipivu cubzhauf. Ey sca alkan wemacuanodu felyhiix, puxw fma juwociSarjh buvwnouz waqf ikm srugfe ex ha nra fedlilojg:

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

Mwoz golf tdivqu niz e vul ulmucb ih yuwjuxsoshu. topapoBapnz us oj A(x) ugudiniox, wefeoza orgiq exexr rimokey, olepd eliyily ukzok qwi zotukel isibivh qalg dzumy mitn gu tuba ev qtu tutgilk rvabo. As bejyvokx, qapakuTonw uz ob A(1) omupirouk.

Riqiqck, fawb ekf arvavi wte civn lavo ih qisebioruvi do ifu hvu viz laqvoh nagdduoh lsor bowojwad mci owpim:

let node = deserialize(&array) // old

let node = deserialize(array) // new

Jue lyeulg coe zfi izanq yeve ggii zapesi ipc atjug cni yutuneuhokazaor jfehixg. Gki sipa vodhyihubd hav tgeb hekazuel ed xoc E(f). Maceumi yie’tu zmaijuk i pes xinestul irtud oxd ypohu i finazkeqe diqiliej, kwul iknocogss duc o whili cucfconefs iy E(n).