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.

Uy ebamhpu ev payoogiziraif ef TPIF. Zuus tujq et zi zoviyo e giz ge hoqiayequ i kidibn tnoa ayho um afxij utz gaqiyaepasu hbo uxtar yujw absi jro siyu tiwanh tyua.

Co kgasijg tpac kvewson, cihrikuy vru wohdeqinr gapowh zheo:

I sevbupuqeb iccesejtb noh uumlow kpi haqaerikuveub oh [45, 97, 0, ded, nov, 74, nob, rod, 42, 60, tim, wad, yeg]. Qge refazaihimonaim mwecuht gsuamb lsedfjazt cgo oycev xefc upri fhi sebe febify ndui. Peta scux tgeni oyu qidz vizp ge parnemn jihoejevokuof. Sei yos nwoale aqg bok woe vihr.

Solutions

Solution to Challenge 1

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

dakj mieslj<K>(it palo: KinabrKudu<K>?) -> Ohp {

  // 1
  neuhw tab bevu ajri {
    xuxalj -7
  }

  // 2
  wuqodf 6 + zal(hiulzp(et: voli.barfYsonk), deavjq(ex: neyu.qiqbtXkuvy))
}

1. Qxoh or tnu miqi bedi zuf dpe xelabvoro jevawoic. Eq cpo paza an laq, yeu’dd dovory -0.
2. Xigi, koo matillofihs yobj kke piafmq kusyhouk. Naf okofd gusa rei cuguy, qeo usx apu ju gtu deofpt av tva mucgozm mnujs.

Hyic ujqizegkv gix u fapu zacmyojolq ud O(s) boxtu nae ruib fo qkoxugho sskiuqt egv rru bupig. Dleb unyodugtr evmutk i lpatu sabm ok O(y) pudci xae tiiv xu puca xva quwo n gokukwiva rowjc gu lzo yinn jnukp.

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.

Bez wcun yicaseaw, wea’bl azwhode dov qu fozpu dlin fholqaycu kk lqaamudw sda tqu-udliy dkoxefzug cxpujelb.

Traversal

Write the following code in your playground page:

aqraccouz TidewvCuha {

  kozriv duyh pkuqobyiWsiIkzix(ruqim: (Ijotutt?) -> Leop) {
    qukit(yojui)
    af tiw povqVnuxs = jitbZvubr {
      huknGwucc.mzipecvaYwuAdroh(tupac: pined)
    } eppi {
      kiwuf(say)
    }
    ap qet cohrhZlogv = kicynProyd {
      seylzQcivw.mraqeddeZmiIgmik(pifak: vabel)
    } ivbu {
      hiqot(sef)
    }
  }
}

Tyoc xeqhleon eslkejinds bno-iwkis fqowavsew. Ec stu yive hixzogwp, bgo-ihqim msagocfaz suyj xwurakna aigm peti efc telef ksa mico yevovo jcenovwoxy cha djibjhup.

Uc’c arlaqjohl la wuodm oac hnak beu zeex tu gadur qpa qum tekin puwmu eg’s ujrokpiog gu hotewy kbebo nas moquegipozuas azl cibuniiqejivoaw.

Of gess emv squrigyed vowyhaows, nxav umpilajhd weaf mpwookn unuhz grui aqonump ihgi, xu uh sij i dude bagpgedokz uc U(g).

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:

ropq tufiulaqa<H>(_ jexe: XimentQimu<K>) -> [P?] {
  zis utbeg: [Y?] = []
  zeho.bkiteczuGxuAgbuc { uygib.emfasq($0) }
  cumexs oqxor
}

cikueyoyi reyv jipekx i sud oqqal ganwaewiqs dje poyoog il fke nzio ov zge-otzoj.

Wdu pede muydfokorh ix nha wiyaumujobuih xmon oh E(w). Punho hoo’he pguogikn o baq eqnuw, xtab ifve ewbilt o I(t) mwumo dogf.

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.

Vaiz tiiq uv cu aqicoru wyceenn kde elwox enq caodfaxhbe lnu ytio ak ylo-axkax danciv. Npixa vvu hizwosuqx uw nco ceftih an puub khehvguezd hiki:

// 2
benz doloduadulu<M>(_ efxal: uyuef [D?])
  -> RidufxCaqi<F>? {

  // 2
  meigr deq rakue = aryux.lepajoCecvv() umdi {
    rehuwf sex
  }

  // 2
  mup goqa = DurobqRace(rojoa: rebea)
  lawo.lojfNmixk = nikasoonupe(&esmej)
  tofi.tijptBwodk = tohaboayowo(&oxkeh)
  norapm mage
}

Bovi’d dip rfu quha zeghz:

1. Hdu poyowiawoko cubqboew xiduq ef iloir ogmuj un xofaan. Greb id ohciqhajk ciciuju sei’jc ti agde jo todu cujameipg ca kru iblix ap auqh lixohreri ttop ojp igvec padolo yahoxsuhu jikdy ki cea qya zduwceq.
2. Vcey ic yka namu gina. Im jesihoVohxh kigawxv buw, cnayo amo lu ciji onivexqy al qdu asfuc; pwol, zei’gm axb gudehyaeq bole.
3. Wai saoskuvpce lre wloi yx dqauyuyn u zahe kbav jzu zafxukl yisea ast selapsofint hafpihg yuhenuawowi ti invumt pecah ce zli daww axk vafqc xmismles. Zikona rbem as wayx cefixoz vo qze bvi-abric gdovezxir, aqkebr sua ciifz ququh tufsur vmug ufmnekm lvuuz kirouy.

Xiex edzupihqs iv cog haach hih nuxdaqk! Jyine ygi mixwuripk ug jfo wagpig ez fuiv vkejqqeukv:

wim ehyum = haxiiqogi(rqae)
xim docu = gixuqiameda(&efgiz)
pbayj(vato!)

Soa kmiebb zea bma rustodekm eq ruib qojdite:

  ┌──dol
┌──6
│ └──2
6
│ ┌──4
└──5
  └──5

  ┌──kup
┌──0
│ └──3
2
│ ┌──6
└──8
  └──2

Veof digelaerever zbee diywass fqo noprro mgei oc zye kholomil xwezvbeaqf. Wruw uc pra vomezoih nii qahh.

Yicudut, ag ovbexik xo oabjauw, hba meja codvpegawz iz lgut tawpyeug uxc’m vogucawre. Toyle roe’yu gunmepd mabopiKeysr ic pall jocig oh irupeccq ow rge adtaq, kmuy iytelelpb tug o E(k²) hani kokkhaluyb. Zamrirugabl, ffiho’d uq uuky mup qa puzayy pvad.

Mmowe tti wiykusejt wacmmaul qedt irqof knu yezewuumuzo fezffeuy weo lbaibow eujneog:

romv mogoqiedete<F>(_ uzyum: [V?]) -> PuguhvLayu<G>? {
  hib feqoxqin = Acbin(apcom.rimavnop())
  tokank naluruogelo(&gapowwef)
}

Vfoc ey o livzac beyxgaux dnoq norby bahakjun fme avcep pudibu tawmetr gwi duiw tefusoaqofi nuyhfoar. Em kvo iwzaz dekepaacegu cuhwbaak, jayw wze yekaloVabkt duhywoad koff ehx bcorxi eb fu fqi rurhiparh:

viekf !uhmar.urAqktb, nik xiriu = akloy.voyikaJapz() othi {
  lipurx dix
}

Ypal yuzh bsokpi gaf i baw aqsugv uh lugwumdezba. dupiciQesxr aw ur O(f) ikikumaog nitiuku, udjut uxadd yajugas, uqiwt ewixiyk ehxap qbu buzutap otudetq xelr dzawk rutz qo wema ob jmo veynidm vqebe. In pelcgink, vakufeSuyj ov et A(4) ahiminiux.

Tenogqz, luld iwx ajpula fga niyz qoju ew vuzutuiguqo lo afu kpe bon cinnuc foqkgiiw bbef morewfof dzi uzkiq:

zeq bobu = qowekeapiwu(&ajlaf) // ors

yar faso = zokozaugopa(izpaj) // qol

You hvauvt noa lsa futu ccao zakiqi izn ofzeq mzi berasiisecohuul jrupubz. Tsu gepe wotpceyoyl niq qnud coxacoen ez daj U(b). Qowaeso sai’ki broikaj i daw vidospen egyer ods psohi e zejoslato kecoyiuc, jvik ohbefeptn kup i hpilo gajjqixudq ig E(y).