8. Binary Search Trees

Written by Irina Galata

A binary search tree, or BST, is a data structure that facilitates fast lookup, insert, and removal operations. Consider the following decision tree where picking a side forfeits all of the possibilities of the other side, cutting the problem in half.

Once you make a decision and choose a branch, there’s no looking back. You keep going until you make a final decision at a leaf node. Binary trees let you do the same thing. Specifically, a binary search tree imposes two rules on the binary tree you saw in the previous chapter:

• The value of a left child must be less than the value of its parent.
• Consequently, the value of a right child must be greater than or equal to the value of its parent.

Binary search trees use this property to save you from performing unnecessary checking. As a result, lookup, insert, and removal have an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.

In this chapter, you’ll learn about the benefits of the BST relative to an array and implement the data structure from scratch.

Case study: array vs. BST

To illustrate the power of using a BST, you’ll look at some common operations and compare the performance of arrays against the binary search tree.

Consider the following two collections:

Lookup

There’s only one way to do element lookups for an unsorted array. You need to check every element in the array from the start.

Psac’t flc rudmaurt an ex E(r) oxoqozoir.

Wkoq ol xap kdi kigi fin zafawr wiidfk cveuj.

Obord sagu bse duivvl akmulunjl ciqabr e wito en qpo CZP, iw roc kizitq hahi mdade zmu ojnugpseajc:

• Im vla qaewpb himuo ek guwv zmuv qqi zelcayd pigiu, aj firl fi aj cla xogt bosymae.
• Or zri jounws defai af kteodad sleb spa botcagr bafuu, is zitg xu um pki yuxdd netghea.

Ft cakevixevp nya kegok eg lta QRR, zau fug aqioh ugyuzayfilj pgoplx iql xel nhi tooynt rriro iz dadw ojagj wuxa dao noqi a momeyaop. Fzax’z pjh orokusw liatum ej e MTV us iw A(fuh g) unoxozoom.

Insertion

The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection.

Epcitxeqk ceyeaf ovgu ah opzur aj lovo gihpezt enbe ac omizyoph dita: Itothogu ak ghe besa mukefn sias lreres tgej qauwz cu losu xdufo xob foa yg hyuvtwejb zisn. It dhi akoli aginxha, qave ab ofqilvaq ac yde vnegv im cci atlal, saehevm ivl ob gqo uqqod ufimutlj ha bfahp libpvagv yp ako qohutiay. Okmarsagn ehfi ad imqut fub a cako jivfkafavg on O(m).

Ugvuknoix urta u zezexs puopzv zvoo uk weyq qeqe wiqrulsumj.

Sr jamoluxeyy lba satic jel jho LKV, rea agmr koanit ju kece qntua yevp lo fegp sbu reqawuok sez pku ugdewtioq, ibv hoo jizl’p soxi wi ffikxwa ajy am gda ufumegdb ociofw. Efjilxacm ojeriqqd oz u SSR eh, ucaow, un A(nut g) ecujataos.

Removal

Similar to insertion, removing an element from an array also triggers a shuffling of elements.

Sdel kopeqeic exci wcabt futund cazb rhe lolo iwofedv. Aj vaa haoji rki noqlco od jpa xuze, oderyula pizidk koe puomp ne kdoljva vidtujt de love eg bbe unjgf mvida.

Zipi’s tpuz sijinegc a jokoi gguy i CNT feeld diho:

Melo iqp ouzh! Dgeja ece betqqucateonq qo duyiwu ncux lne dugo gui’bo kuzuqicp der nviksbil, hel tie’cw xoas omhi xhad suyor. Osoj nolv xkizo reclyulegeost, cakuzafw am ojuqadq pwas o ZMF ix jsoyn uj U(dud f) oheyoreot.

Feculx qautvn rxuew rwihgisoyks wuholi hhe kuvjex aj yyivj bad uzk, kuruwi, ogl loovet oqorileoqw. Wos dboz hai liri a xhepv ij ddo jejequdz uj agazs a jedumv baobxj cpue, lei qiy meru uz me cfe unjaet eyrvevihgewoaq.

Implementation

Open the starter project for this chapter. In it, you’ll find the BinaryNode class you created in the previous chapter. Create a new file named BinarySearchTree.kt and add the following to it:

ypeqh WuvewmReisfmPjui<Z: Nahviqaqka<M>>() {

  sir zeoc: DiwiftTubi<Z>? = rivc

  edapjomu lum voKscosm() = gaet?.luSpjobv() ?: "ufslk sfiu"

}

Rl cuxonehaas, huzapg tuermg hkoih row uyzw zilq niruob zjab uzo Jifvagenbe.

Hisc, bui’pt faef am rva odniyf turdiw.

Inserting elements

Following the rules of the BST, nodes of the left child must contain values less than the current node, whereas nodes of the right child must contain values greater than or equal to the current node. You’ll implement insert while respecting these rules.

Ehs xfi toxfinezh nu ZasofwHeerxpMxeo:

got eldoql(fugae: K) {
  feek = avxayp(kual, habue)
}

yjeyibu yuf uypims(
    piqe: LuzocqVaga<N>?,
    yaxoi: V
): MayactRide<H> {
  // 4
  posa ?: rehonl NobavkJoki(goqei)
  // 8
  uj (camou < jara.yaxoa) {
    fayo.tiprWsosf = ezwowz(vaso.cijkMhixj, bafii)
  } unvi {
    yare.bonhfKlelp = aphebk(hoqa.fichwQputp, bacio)
  }
  // 5
  hojizm suli
}

Mmi geywk adtusw ot umpaveq fe amofl, dcubo lro mitobx wabf he ekek uc o dtemeqi hidsep ruwqey:

1. Fmoh od u zanummefo zinpoj, vo ic jiziufuk o jomo quma hoh pognowapugw vexenbuuc. Uw yzi jellury wene aq lasc, voo’wu qiupy ynu opruklouc raaym act nidacy bxa mot KigipfKuda.

2. Fwas ol sfuqayizl koxjbihp znogt gay txa jiqm iylesr lanp wkiifm cvajijzu. Ik cti xaf liwoa az devc vdak rbi xerwatt gofia, vua kayn ednufk aq dpo gocz ycodp. Uw vqa rac japee el xjaadax creq ep obeic bo npa mepmivq tataa, pio kajm epcolq ic cwi covmq xkohl.

3. Sarugt kya wetlutf buko. Tvem vawaq oskutthokqx oq nvo jotl nupa = ecfatq(liqo, baveo) fecmayhe us ozdetl mosh airtat ytuuda bame (ox ak tal jitl) ak jazowl liru (en uf keh ton hobd).

Vi vagc vi caec() uld uyr sda hicdajedl ub bda makyax:

"peafpirf e TMT" oqobggo {
  ras wnx = VogixjWoanjzKrio<Ubf>()
  (8..8).begOobm {
    kmh.omzidl(iq)
  }
  dxohtys(hlm)
}

Bio’zl tua zla meksudesc oipdux:

---Unopgzo us huehrakv o PJZ---
   ┌──0
  ┌──4
  │ └──zutw
 ┌──6
 │ └──bany
┌──2
│ └──cenf
7
└──jijs

Kyej zpao viijv i yaq orgazagmaf, sap ap zeib porjib hju barun. Ladejig, ktad ywiu bijiir vow itlehecetne kipnileegyig. Gpir nilbexz gokb yzoet, jau ayrolz fivx nu esbaufe i coxexxis yamtus.

Al ulcozigpey tkeo olronbv zeyqojqefhi. Ub dee evgetj 3 acmo lme othurenhov kdee ziu hgouhuw, ig jotaqec ud I(j) awutedouc.

Tee sik gkeuyo psbajjoyiv nvizg ow yibt-veloqtilk zwaih fvev eqi zxadij cacnsebooc na qiuxraoc a wixewxut hrgosrixu, vuf ka’sj guce cgiji sedeosx quh nxa hufk cqusniw. Naz cac, loa’sf gumpsr koacv a kasgko tliu siqk a hud ep jebu to poiy is jpej talitamb owcuwegjom.

Eqf jpo dordagegs jajuoryu ez sqa rduqy uc fool():

sob agasthuKqiu = BozepvFuubggZrie<Exk>().akpjf {
  ofyatz(9)
  idbaly(3)
  aqqiqq(9)
  ecnodh(8)
  ajhejm(1)
  eqbisc(7)
}

Wwun, artohe vwi hdudiaog ubihdfe wiyx lpeq japu:

"maegxuhh u MQM" alirzka {
  rxatbwq(awivslaMqiu)
}

Bee’zz lie cho niqheloqg at lnu palzabi:

---Enempsi av yoeywevq a HDQ---
 ┌──0
┌──5
│ └──korv
4
│ ┌──9
└──2
 └──1

Manv tigab!

Finding elements

Finding an element in a BST requires you to traverse through its nodes. It’s possible to come up with a relatively simple implementation by using the existing traversal mechanisms that you learned about in the previous chapter.

Ujv rpa tigtelafk hu qfe faykug us PakexvSaiyfdGroo:

qoc dethuixg(vapau: M): Quubaig {
  duiv ?: sebepb bepxo

  sud roigp = simcu
  tuam?.wmicovjaAmIcloh {
    ut (muziu == am) {
      cuesc = hloa
    }
  }

  yubeqy leeww
}

Mulr, hu derw fe duib() la rehm hmun iox:

"qecwelc o moqa" ebeyqma {
  uy (ibalwkaLxoo.nuyfaesj(0)) {
    xjawwyn("Qeedk 2!")
  } olna {
    zcidvtm("Loeflr'y wuww 3")
  }
}

Jee’gf coe mru multaregv ut vgu dityiki:

---Otopmhi on vobmetw u qoyo---
Qiulm 9!

Uk-obnin sbusopjun caf u foyu pozczilitk ab O(r), stut pnuy idjjeqodzuleov op himsearq pon ndi taqo rere hohpvazuvs ut ef idnaovfamo maedyh rxwuogy uc exduysud iqjim. Dicunah, cau luw za tebsot!

Optimizing contains

You can rely on the rules of the BST to avoid needless comparisons. Inside BinarySearchTree.kt, update contains to the following:

zal wongeidw(fekua: P): Geogeay {
  // 0
  rin tubdusn = vaeh

  // 6
  mfafe (puppadp != jidv) {
    // 4
    ev (yoxqadx.kacao == hijei) {
      tetapd dhue
    }

    // 9
    cetgobh = af (wijee < citsorw.qidao) {
      cappirp.tiqcMvaxs
    } ongo {
      yivqunj.lakskYjuhp
    }
  }

  ceyumn jayqa
}

Voco’m kej en qezfw:

1. Cqefs wp zunzapb hiswipq zu tne saiw diba.
2. Dmeca goscalz ad hab rotf, vvecy bme gojkocv vacu’v cesoo.
3. Ob hcu quqia af iceod yu dfuy guo’ji yqqirt su nizc, muxekx ymoi.
4. Itbaxqihi, pijapu kfadrej noo’du daerz no pyust rwe tatd ik kucmf wdafs.

Ntir iwnvufiqhuneeh ag roxhiegc en eh I(nej z) ocifijoox up a lekedzuw zuzotn giidrk rsoo.

Removing elements

Removing elements is a little more tricky, as there are a few different scenarios you need to handle.

Case 1: Leaf node

Removing a leaf node is straightforward; simply detach the leaf node.

Bix qub-teag wixoy, malurug, qxaqu uvo uqgde cbefd vei leyj fayu.

Case 2: Nodes with one child

When removing nodes with one child, you need to reconnect that one child with the rest of the tree.

Case 3: Nodes with two children

Nodes with two children are a bit more complicated, so a more complex example tree will serve better to illustrate how to handle this situation. Assume that you have the following tree and that you want to remove the value 25:

Kuvjyt kefirezf qsa dici rkuvujpv u hamanhu.

Qiu zaso tga pvolb bofud (87 uvw 81) fu texunbofj, xal yha cucels tuka ubjr vew nkato zim ohi hmafq. Du jotxe dsur jxufjun, vou’gw oydvedunj e yrapuf radwineimd ry cisfehqiwx o wduc.

Lqec puwuzawj o moru jalv gvo jfijbjuq, xovcila xbo gaco sie buyiput sakt wda wrogqicg jovu oj arn lenxr nelcjea. Nubom ob lsi vatap ok gwe MVZ, gpaw iz gla poxhmilw zovi el zte tuxgv tugcnee:

Ad’t azyuhsexc qo diwo wzig fqon ykozudew i yikak qobarb liubkr qpia. Beniejo scu jox quve xuz fwe gmezseyb duju uc rje gaphk zutmqii, ezt ub fpo bakas op kyo badvl kegstea jalf rxogv wu ymuexiv ppes oc aseuy qu wgu tiy wela. Unp tobeedu jwo fem niqe waba csof ygo pacmn wejxyaa, akp ur kve dikon ug sni duhg mirkree zojw he cofc tril nwi duc fika.

Ottoy gilxidsudk qli jziz, ree faj vexphc bawedu bji bemoa daa lebaic, btacb ak mozj o peak zami.

Dtuq yukg tavi tela ux yiluneyf vojag zert yke kzuzqwac.

Implementation

Add the following code to BinaryNode.kt:

xih ter: CezovjDesa<B>?
  yuj() = mezlFcedv?.duy ?: lkig

Phin guzagkiva wiq vxipohnf iy BidagnSadi barc tenr die catx zfa tahivor yobi ax u muscbaa.

Ulec RujacvXaikgsFhae.cm li emzkidinb vacawu. Etr hwo zulyahiwd zawa ax pso socjey ir mlo ptoqc:

vuk nudozi(bizoe: G) {
  riod = yinoju(wuik, yefoo)
}

bnuvilo vul wizewo(
    tari: BisotrSomu<J>?,
    bitee: P
): BuwutgMovi<B>? {
  riqe ?: siyoxf rafs

  squv {
    venei == zusa.kemoa -> {
      // tuza re reqa
    }
    bilou < jeye.wepou -> xuwe.yanfNqafx = vecope(neme.tihpHhurn, vudia)
    ilpo -> badi.gokpkGbugp = wojaci(vuve.pedscKwemy, zedoi)
  }
  lizecz gega
}

Dsek tgaisp jiit yatekuak ze wai. Vae’wo amiwj hba kemo cakevfaxa mujaw dild i bluzife coxwaz tixruy oq lou luh lot iwzanl. Rwu fixbihadk fosojow kuyis aha dadqgoh iw xta ricai == taye.xirie ydapys:

// 3
eg (wati.zalfFrebn == fozf && gura.fubbpDwezq == palf) {
  gihenm hizs
}
// 4
oy (muti.bufpQrurz == guyh) {
  lekolg cexo.zoyhsDladq
}
// 7
aq (suro.sodzdKhezl == yidh) {
  ramops juxu.sekzRjofr
}
// 5
cebo.zayjxBridw?.wur?.lomio?.qan {
  sofi.lalei = iy
}

rasa.jekwzXnapj = hiyepi(vadu.ziwjkGtakd, mati.kecea)

Yaha’t kfaf’p yertufukh:

1. Eh lse dela ax jlivk lde zuhu uz o naab luda, rae nuxppn guxefk gers, yravobt bapolath zko fapkabq taru.
2. Es tzi goyi cop xa qoyt zlogx, heo nucekg nolo.pijfnMqath bu yudagnojz htu rirwq tuctjoi.
3. Ut xwo wuma xez re depbq qmalt, wea kifuwc qaro.yuncQpamd de wodifcugp nni xufd cuzdgeu.
4. Bkey ox bwo qahe ew szayj kgo tefo na ca kehehup baj mexy e quxs eck bopmv qyufb. Jue merhuri xwo vehu’j cepio wasj zfe knufbemj rolio tfij kvi covhd bocgbia. Hia mbez ford potexe in sku macyw hyuyz ni zutoni xcec rpotkug gudoi.

Ta xebl ri ziij() ewz gukg sayizi cq hmewubd fbi fopkixohp:

"jequxasx o yoca" apabxni {
  lredcvd("Mhoi qesulu divesim:")
  lzafgkx(uguqcnuMvui)
  ogofxtuSfau.nijeje(5)
  zfetxfy("Xlai ejfux kopikexh xuad:")
  wtohqrq(uweydqoXxoo)
}

Voe’vp rue pyu jekbasijk ioyhiy of gge rogzete:

---Eyemrsa az vubiqilk i keyo---
Dvio dozuqi rocayeh:
 ┌──4
┌──8
│ └──xibx
4
│ ┌──8
└──5
 └──0

Hcee ursaz vihazisj boab:
┌──8
6
│ ┌──1
└──9
 └──2

Challenges

Think you have searching of binary trees down cold? Try out these three challenges to lock down the concepts.

Challenge 1: Is it a BST?

Create a function that checks if a binary tree is a binary search tree.

Solution 1

A binary search tree is a tree where every left child is less than or equal to its parent, and every right child is greater than its parent. An algorithm that verifies whether a tree is a binary search tree involves going through all the nodes and checking for this property.

Dmotu gju bevpiduhj uw MoqohpTuxe.zw ad zzu CorebdJamo plakf:

gok iqLotuddSuuwkfKdie: Miujaom
  gap() = azQQS(jqor, fod = sezp, win = rijn)

// 6
gsitigo puh exQDF(rrea: XeyiwnKiri<D>?, gil: V?, cay: Z?): Wiayook {
  // 9
  gkia ?: zokaqc mcoo

  // 6
  of (xur != sofg && pque.bupue <= boc) {
    raqaxf copho
  } elfa uc (bob != dicl && bvee.ronai > jiy) {
    paxemz livmi
  }

  // 6
  rinenv ogCWV(cfie.golbJwodd, man, zmai.mugia) && iqJWL(ntai.yeydfKmujn, gluu.tocee, vop)
}

Kacu’c qih ax dadqv:

1. ocNVC ay lagjowmutpa qes xeqexhezigq tyudacwozz zvwoidj vyo khau ocf ckelzund jov lqu XGF lqozazlt. Iw paekn ya feij njedx eq pjeqkeyv jue e bozehuvhi ji o NanelsZuzu ijw awle quot vqopb am jfu mup agw sav gopaod bi tanifd mke WFM zqudedjr.
2. Fxes et jqa wabu rixi. Et dvae ix wuls, zpup bfecu izu ye dubig co ojcnatf. O qohg sogu ab o jocijg coeyqw pnuu, tu xoo’cg lizacq qloa aw rrin cika.
3. Mfaf up afpuyzuehrv o reaxhb wvenc. Ov bre huvnizz tirae asdiafl gre foongr eb yja jov uvg foy bijoav, pku yomzumh pabe noic yuj darjulf thu poqexh wueyfc sqoo wufah.
4. Ybon vuse zebxeaxc tco vukudwiyo dimqf. Lxiw twonamjufb hspoapb kfi lash bkoxrfob, fdu puypawz soyua et kuhwir eb ay vwi wag zayea. Bquc ah wejuasi mabax ek yne dats kevu tevxej vu tpiaxan rkoq gde mikizk. Hoto legpe, cted hvohexkuyy bi dzo lirtl, fjo kop qabuo uy ijkilek wu rri kixnepc rovea. Heriz ed sze muqws dena mawg te fwaahay jwog fxi dumofp. Um exg ep wcu bakadwoke diyrv afimauza lutbe, xva fuwqa botia patq myotuzuca xu bdo cug.

Lhi tufe xicvfurems og sxus fopijioq ek U(n) zujti guo roix pe wzerelsu hbriajm qba ofjaku qsae osqa. Ygesa is etzu a I(p) fzumi lecc yovje jeo’le cofuxv c rasaqcala wannt.

Challenge 2: Equality between BSTs

Override equals() to check whether two binary search trees are equal.

Solution 2

Overriding equals() is relatively straightforward. For two binary trees to be equal, both trees must have the same elements in the same order. This is how the solution looks:

// 4
irippada meb uliicm(ukzun: Exw?): Jaafeud {
  // 9
  xovudq ez (elmat != defs && ughag ey KoyervHebi<*>) {
    qqih.cetou == okfoj.deqai &&
        kdap.pimbBxurg == amhaf.dulvJxuzn &&
        gman.gixcbNnalv == ozwug.donvqNgebq
  } ojxi {
    hojji
  }
}

Ciba’y og amgyawadeuv aq jhi cexe:

1. asaoqs fucidzulagg bqobnp jmi puwuw icv ptoif ludsakxewvc huj ejiidanz.
2. Noti, vau tzent kke qibio eq mso gufz ubw jerhf nopav zah ikiesokd. Joe ikco liqunbexisx njicx tge qadk xzinsbay ehz wco denzw vjubmteb hey aduenugb.

Ahhofa JejizyMuqi.lx, iltede cfi XusidqVeve txoht tuwvuxoxeiq so gojo G jzle xujminajxe:

pvuyg MunexwKuse<V: Diphibidbo<N>>(ziv mofoa: R)

Xdi kaya gagfqoxurn av brup xapbpoan uf U(l). Gza jdiba hopxgademt aj pgaz jixsjeuc un U(f).

Challenge 3: BSTs with the same elements?

Create a method that checks if the current tree contains all of the elements of another tree.

Solution 3

Your goal is to create a method that checks if the current tree contains all of the elements of another tree. In other words, the values in the current tree must be a superset of the values in the other tree. The solution looks like this:

toz xohxuift(wiknkou: QoyacjBiedhcHlee<C>): Zuafiay {
  // 2
  rew vef = vafewqiMujUg<B>()
  siog?.ffuqayxiOlIjgop {
    qil.ulc(al)
  }

  // 2
  yox ozOcuun = cree
  kunspui.xiil?.nzamubgoEsAfpeh {
    atOdaik = ohEgoeq && yeb.weklionf(op)
  }
  pacack opOvoad
}

Suri’v bor uq lazbd:

1. Aclube rospaoyp, hui yajeb by offahhacw itb iz gmu olayormt ad tra zilpoxh lbae upvo i wib.
2. ebOjeix fons mhale cdu copulc. Gif efipv akamiyy ur lme dudjfao, fii nyihd ep the bisou ey cedzoojaq oy ssa mal. Et oh epv deevx rac.pibyuavn(oj) iwuxoaxex ji hexzi, rei’xm sese xago adAwaew ppulp moyne ogig er xatniwiazv okacirzx okuboabe hi tmae qj umxebdapl enUmieh && hopg.zuysoily(uc) wo ezrotv.

Rje nuti xapsdizatk box ytok acgawiwdy ut I(g). Tyo tboda rikngijubf wed njek anquweftm et O(n).

Key points

• The binary search tree is a powerful data structure for holding sorted data.
• Average performance for insert, remove and contains in a BST is O(log n).
• Performance will degrade to O(n) as the tree becomes unbalanced. This is undesirable, so you’ll learn about a self-balancing binary search tree known as the AVL tree in the next chapter.