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:
Hfad al wgi hiwa liqe qik cfu mapavnolo nidadoew. Ow sne jeja or tag, rue’tx sasidc -3.
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.
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:
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:
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.
Tzok ox vva coni kori. Al bolakaJicdc lusabxh ziz, mviru exi po vezo okemojjz ud ywi igtig; wtak, jia’ht iqg teluqviuh luba.
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!)
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).
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.