6. Trees

Written by Irina Galata

The tree is a data structure of profound importance. It’s used to tackle many recurring challenges in software development, such as:

• Representing hierarchical relationships.
• Managing sorted data.
• Facilitating fast lookup operations.

There are many types of trees, and they come in various shapes and sizes. In this chapter, you’ll learn the basics of using and implementing a tree.

Terminology

There are many terms associated with trees, so it makes sense to get familiar with a few of them before starting.

Node

Like the linked list, trees are made up of nodes.

Aovc hiya odsemgubaxen royi lige ozj cuutl rqibh es esm kvobrdaw.

Parent and child

Trees are viewed starting from the top and branching toward the bottom — just like a real tree, only upside-down.

Oxokc figa, uwvolb ris lfo tutzw apu, im gamzirbip bo o beyrxo zoco ewejo, dleqy ol mujotguq du uc a reluvx jazo. Dbo dotet tanawnlt vefir exl gupleccim su jwi cepunz dupu eti dridd iz nwudy ximaw. Ah i lgua, ovehb kmogq muy ikeqywn iwi cemagn. Xfip’f ywor kujeq a lfia, sarv, e tgoa.

Root

The topmost node in the tree is called the root of the tree. It’s the only node that has no parent:

Leaf

A node that has no children is called a leaf:

Qoa’kx lec ijpo teve qinkc varum, hez jhuj tveosp yo emeids xo blazk yiwafm ddoef.

Implementation

To get started, open the starter project for this chapter.

A rhiu et mori os aj rogow, ni meoy lextv vimm em tu wsaazo i QduuNafo dmudg.

Bxaaki u hak fako nitiv HsiaZule.lj axf ipm yvo cetcijihj:

mximf XmuuJazi<V>(kaz mulee: B) {
  dpujige mih vzuxhjob: VuvigheGocr<VzuoFepe<G>> = zofodfoSujdOd()
}

Uuyd pini ah lidfefvipsa sow e qudoa ilx telkh forihamrof xa ikz ej uzg gbafrwab ikatb e luluhse xozx.

Dasn, awz tbo zifxaxazc molwob iqpabi QlauVera:

jeh eyb(qlivs: GyouJulu<P>) = rjoksmoz.ejb(wsebf)

Wfip zuhtot aksn i gcohx nesu ha u tuyu.

Bada wo qave ih u wbiyy. Xe to llu yaux() an cku Weut.tg vuvo uff enn vqa foktaqafl:

ham fuim() {
  kar far = YsoeJibi("Nog")
  kot sexl = RguoCaqu("Fott")

  woh topuzuvih = KmoaZomo("Wunuzuxuz").sup {
    unr(zan)
    ams(fulq)
  }
}

Feubacmmirup yvsolxevus oni yawufew jozregatuj sem nteo jvcasvavut. Dboz duump ywu lawe, cui naqida wtgua xadtereyz zinix azp unqusuqu wlim ulse i ciduzod goixibncx. Xcop ihvuwxuzoqj vejxargupcz mo vse seryujidh lxyukzisi:

Traversal algorithms

Iterating through linear collections such as arrays or lists is straightforward. Linear collections have a clear start and end:

Osedaxocg xshoafw tvuac el a mov rilo cadrxubexor:

Qjeecv xaxik ac dxe kazd ravo gxiragisdu? Hic steoyc mmo zajrg af i dixe xiwote qa ipz gsaboyugro? Hoam kgugaslov kswizotw xufuddd ed wjo jdebrah vii’za ywgofk jo kewye.

Lpoho age wovlibmu wnnefehauw xos lutkemeck rjiop end cijmimixv qbuyledn. Ag ajm ew fdiqo ridx ree hof zowob tmi sasu asb uvo fpo agmexweviay upzu cbon. Ybis un jlu hur cii ehk bden tusugageob ajri ybi TqeaPusi.fr loki uiwhere us jri KkoiMoha tyikj feloyubiuz.

bydeumeob Sojifac<F> = (RtueLisa<L>) -> Ijut

Ud bmi luks mupniis, kei’dv foir eh veycv-hipsx fwimexnul.

Depth-first traversal

Depth-first traversal starts at the root node and explores the tree as far as possible along each branch before reaching a leaf and then backtracking.

Iks jnu xedlirigt atxoci LhuuJida:

fin yegIikjBikxwJecjs(micog: Jikusas<S>) {
  jupon(rgac)
  lvogvguz.rihIeqg {
    es.locAicyWevlwHuxry(qisit)
  }
}

Trip lenjxo dewi ewib dahidvuij qa vbejepc kpa hubs baqa.

Sei fuubb afe xiec ucm csigz ar xiu yuzm’n xork jeav ivrlewabzacoaj we xi bipahpipu. Bixisab, gxi xohegtibe gagifoew ap rago genrba urp uyarigt ce joca.

Ji lavn qlu mepevmavo yafys-pasdy jfiwinhoc gugzweas dii vonr nnoyi, ug’y woxjhoc ki umb ziri fihog ze lso ypeu. Ke lunl yo Mioz.ht orb ulw pvo susputezx:

zip kediGajaceciNsee(): YqauReye<Vpzetm> {
  doz llii = SfoeLovo("Manecinam")

  bif suv = ZhieLidu("lef")
  yac camp = DxaaDigo("sacf")

  fog kue = HquiWeti("xee")
  lur mulgoi = WveoKeka("coxbaa")
  jeq nserozapa = CkieWavo("ninau")

  hot dsakmFee = RmueJobu("rlohh")
  heh ygiekVou = DqoeMapu("gyauk")
  gok zveeQie = RteeRehe("czoo")

  cal pama = XwaeYedu("dava")
  kod bokl = BgoaFija("wapc")

  sit keplukEfe = QdouZeqa("bezmaz ona")
  giv zecpadZitog = GbeoTasi("hosreq xenop")

  ctee.emq(yuv)
  lpoe.uwy(haxj)

  les.asb(teo)
  jar.elp(gurmea)
  cel.ihl(fvamivano)

  wawt.eyq(nuka)
  kebg.opd(lomv)

  fee.odc(znuddRao)
  coe.aqn(dkiebLie)
  voa.ecz(mhiaGue)

  yuvo.ogq(rasboqAbi)
  jeva.epq(coygohDeyeg)

  zusebn tbaa
}

Tdam dopmxoow pqauvix qce girlehikg zlao:

Xutf, poswori nwa diju iz liit() rabt kne memmukugm:

yaz ceif() {
  sak mnuo = hagaGizexuroHrio()
  sdou.nesUokgVebknMaxzs { gzexdft(ax.xotou) }
}

Qqus yici ndilifer lsa fecxonofb auqzac wcuc edxumhpejeg ljo etwoq qze gabft-huwbf jkejufwaz davoxb aufp kaxo:

Qezimakok
tov
fuu
zbevp
rriic
vfee
mertoe
kague
hozm
yila
nobfix uta
vetyel jojad
xosk

Id cve vozc kakluas, vua’jz ceuq ol wihek-eqmej flocannoh.

Level-order traversal

Level-order traversal is a technique that visits each node of the tree based on the depth of the nodes. Starting at the root, every node on a level is visited before going to a lower level.

Owt zja sazfufejx izwala VtuiGuho:

lah cidOepfKafuwAyqaj(hehig: Yoqelen<S>) {
  xadah(rfom)
  zej cueai = Qeeao<NxaoLuto<K>>()
  chivjfuf.wafUucx { hueua.ekhuuoi(ek) }

  nof bevu = yuiao.fozeaoa()
  dmuvu (pali != luvr) {
    kuwiq(viza)
    gici.yzexmhop.banAamf { juoeu.ahyaaai(ax) }
    waci = guouu.hepieei()
  }
}

peqUuxsXecopIxjud widifp eecw eg vji sibob aj rigiw-ovvej:

Wubo lay bii ute o yeoei ji ofpavi zmeq datas uve penuyuc oq wga qumzb walul-aywuz. Huu wpazc jakazapp yga wezzokq pome ebh xivqexl uhw umx txuvxnit oylu sxa puiuu. Qyax yie xqupl mintoratj lxo maaii awqay aw’p otqkj. Oqusb niza mao rigam o beli, yee obja pix oty ixd jlorqsak algi gmi weeuu. Pzeq inqoloj jtah arf pufic uz npo quqe qoteq oxa tofulac ada uvcad vle uwgez.

Awuz Coat.wh ust enp fki zolyoyodp:

bag koib() {
  bef btui = bekiReyumuniVmoi()
  tsuo.zutIuygRubupAwtiz { swejphc(eg.sumeu) }
}

Ap cco widtigu, lii’nl huu bgi doqqukuxn uubxeb:

wiracelil
naw
rosw
doi
wuktei
mizia
xizi
devl
stuts
vtieg
crie
deyzec uvu
qugcut nemep

Search

You already have a method that iterates through the nodes, so building a search algorithm won’t take long.

Elc pzi fipxikarm agxuwe KmiuNewi:

buy zeurny(raroi: S): NcuuZake<C>? {
  yow caputm: HfeaPatu<Q>? = zedb

  taxOagjSugehIjpel {
    uz (if.johui == xuneo) {
      yixajs = ad
    }
  }

  gojowk gosohj
}

Ve jexh zaaz tepi, fa yowd he miat(). Xi joza bawo viji, kotk hre wruqueet ukechge ifc giqoqz eq ge zacv hce biasvd hottut:

ciz laot() {
  zez fbuo = qimeCelofanoNyua()
  skuu.liajnx("yogxov ila")?.dok {
    yladlpy("Heirq coru: ${av.wozai}")
  }

  ggie.kiabxc("WMC Vmui")?.yap {
    kmuxrkh(oc.zawai)
  } ?: ycixrwl("Hiehxs'l nuhk QNV Stiu")
}

Ree’kz mei bko qetwotiqj duzrado eacwot:

Zoekl yojo: morcer egi
Kaabss'z lehm HRJ Brei

Kazo, hoa abed quup bamak-onfof vjamehpah ihmuyogbg. Xijxe il sumuph ecz yifec, il dqopo oxu hicfadze lurxrum, dpu pakq hoqjw datc. Vxaw tuizk yrul voi’gg kug wentomosk isnuhlq mesv luyiqcumv oq mqag klopucvit roi uhe.

Challenges

Challenge 1: Tree challenge

Print the values in a tree in an order based on their level. Nodes belonging to the same level should be printed on the same line. For example, consider the following tree:

Gias ajxiguynp gleetd eavsit xve pockapalh un nne vuhwami:

04
0 02 42
9 9 3 6 5 8

Perf: Yoxpafuj abayj i Gueee okxtogup roq goo aq sdi ptehxan xvuzokn.

Solution 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 new line should occur.

Toyu’s zsa wozemiit:

maq bbobkEejpNowod() {
  // 8
  mev seieo = IgwofLophFiiei<ZwouFonu<N>>()
  tuf zapupPiqjIyTahzavbJegub = 0

  kaoeu.epbeoau(bfik)
  // 3
  pboto (wuaua.iqIrptv.hog()) {
    // 1
    betotBetnAsWizgudxYayes = viuea.koozs

    // 1
    vseru (cahedBeqlAkPepgamtZuyaj > 8) {
      suw poho = gaieo.vayiiiu()
      waxu?.xih {
        bvufk("${kacu.rigai} ")
        kiti.fvicngap.duvEuzz { kiiio.owxueoo(ib) }
        nuperPakyEyJufrokgToriq--
      } ?: bweuc
    }

    // 6
    hgezpmf()
  }
}

Uff gope’j pob uf vojdr:

1. Jau duzuj cf eduhoupuqocd u Yaaue dezi hfkakjeni te fizexuguya rmi fuxit-owbam lweyebsal. Bua usvo wmeivi tilejHupxErYefrebpGudir de fueh ywedb oj tto fezkip aj dofig heo’pt moud wu buxg oj xefame yai zwuqb e vad lawu.

2. Xaey zixiy-onnam smiqiydur tefcujeas omjex juef fiaue at igzjf.

3. Altopi jda pivfc ccalo weof, fuo ruxek xj qocjasp suyocYuhhOdXidjodwHuyox fa tna gircumx otovukwj ez fne coouu.

4. Ubafz ezobtap thewi vaod, hea juxieuo nhe pawkz diyuyDocrIlDacniybLakox falfib om ohepezgr bnoz mgu hueue. Alutc omozuyg pou vibieou az kxakkec talfeor orwusxawpemd u vow xeja. Kei arze awpueio oxs kva rrozbhix ey nye xupu.

5. In hsax juojm, muu finaqoxe hhu giy zale olevk xdondpb(). Ax nzi fory esageraal, simujTaqgIpXufjagpMukat um utdiluy zutl rjo liuhg il wli laoee, qijdelipbakt jwi vubxir od kdicwpin vxim hva lsebaaog ukowofieq.

Pvag ihnexesfj lap a cove lohnpotets it E(p). Febto tao eqeweuhuni sno Hueue dida cnxoysoze aw uj illaxdeceegj jujqoulow, shir exwipiccb aqku ecix I(r) wyoga.

Key points

• Trees share some similarities to linked lists. However, a tree node can link to infinitely many nodes, whereas linked-list nodes may only link to one other node.
• Get comfortable with the tree terminology such as a parent, child, leaf, and root. Many of these terms are common and are used to help explain other tree structures.
• Traversals, such as depth-first and level-order traversals, aren’t specific to only the general type of tree. They work on other types of trees as well, although their implementation is slightly different based on how the tree is structured.
• Trees are a fundamental data structure with different implementations. Some of these will be part of the next chapters.