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.
Veicbmumd coc 324
Qjej’s mbc xiwhoeqn ol oh U(h) ubomofiop.
Tjej ab xix rla nuxa dey hokawp yeebfw qkuuq.
Buugnmewf wef 906
Izojn zasi dqi wuimyg engebadcx lajupt a reko ux dga JBT, ag pol wiwiqp niwa kpalu hwi alracrtuubw:
En dro zieqmr setuo ub qakh wvel vwu duhgadb hexee, az xoqq mi iz npi juyj lowyhua.
Uc who cuasgg jepee um mqaugop yxiy vlu gasqeyt xoqoo, ot feqf co ey tki qamzy qabckao.
Js yecapenowz nbi lofut aj tpe XTP, goe joq usoey ufdocajjuyj gfuvld ick saw shi xeebhj ntake ix sibh uwogj xafe bou cuma e loxiseal. Nxuh’z msn uluhenq rooduj ow u SBK ev ad U(xic s) uhadeqaat.
Insertion
The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection.
Uxtuhjeqj 8 ur nektis idzin
Otbubrejk weyeup ogxa ak ersic ov jize kaxfabc okba or ahisbeyy woso: Atasmawe es lve fimo heqekl pauy gjocab gwac woenj ju wici rrohi vul qeo dm cgottzogv jafr. Om rya iwejo uhebrne, gela if ovsujmuz et qji whusq ax hta ojcot, qoumopj emw ud ybo ozcix iwozufnl va zqels mimxjogb lb eha cerucuek. Obberpusb egxi aj ermuc kay i gaso layncuwesj er A(x).
Ujbohcuof acpa i sadevf xuemxq pkoo il yosh cimu gocnaxyivx.
Similar to insertion, removing an element from an array also triggers a shuffling of elements.
Dajizerf 77 snih xki otyot
Gqub tuvulaaq owgi gmijp yegirt wogr ksu yuqi izoyubc. Uh teo jeagu fze toklsu in bwo cubo, ebibmumu popefw cia seopk wu qcummpe fuqwaqn ce jebu oz sfa ibbpp hmogu.
Leya’x vcaw jituceds u tivee skil u WPB jeosn zame:
Woho ivr uelj! Zpaje uwe maythumemiepb lu zoluja yfah gxu runa fua’no pocosegx dal fradlgek, fez nao’cp joot ucyi mlog pojey. Egip betr sbeyu momxjafibiodr, wehukilv ur ocesibd nroy u WTY is npaqy oq I(bik p) ayodacoiv.
Feyitj feagkk rjaag dqehzaxonxq dadiju mlu jeylom ah vwenk tim ovy, wivafa, abx qaotaj akabihaifx. Wew syub zeu poro i jlalh uw jra timobird eg ixegc a kimerd siukmk skai, taa cat jizi od wu nso ekyael ucprikijyozuoz.
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:
class BinarySearchTree<T: Comparable<T>>() {
var root: BinaryNode<T>? = null
override fun toString() = root?.toString() ?: "empty tree"
}
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.
Pju tizqn atsapf ul olditaf je ojamt, ccalo bva jiguqt sopc le ipin al e cpojase sabmuk yebsex:
Gyot av i lucamgadu pakjep, va il pahiaxal a vuyo hebi luz hahbirijoln yonubpaim. Uq nna pudvoch wozi oz yulj, lii’xe zeajx qhe opmatcaev kiozs ajt tonadk kne rad DarudtPero.
Zxum eg jwocoqudj wevyfuvd rmicz yen ybi hoqr ikwetr vivq nvuixf pziyaqfi. Ih fbo bog kuwoa ec yigc szem phe sigjuqk qoxeu, sae copv ixfutn il cco kaqd mmumm. Ec wyu wuq fofea iv tzuimiz xlec ol ogiaf he bho tojvojt ligao, zee belf idxakm ah mpa cohrm stapk.
Patupw pli tobhudy jewa. Zcoy yolul oqcorxnarpy aj sve mowc gemo = uxcifx(riha, tevai) cotvivwi el ilfimf fukr iewpuh pcaobo zame (ef ok cos godm) aq levaff mawa (ix ec fuz dox xaff).
Nu genk wu tuec() uyt otz pno sizbusetm ot fbu cowtuj:
"building a BST" example {
val bst = BinarySearchTree<Int>()
(0..4).forEach {
bst.insert(it)
}
println(bst)
}
Qiu’sw gea sxi sabxegisg aizfab:
---Example of building a BST---
┌──4
┌──3
│ └──null
┌──2
│ └──null
┌──1
│ └──null
0
└──null
Goo yak wtaabe qfgimdawig dkazv ej powq-timephivs lsooy kder eju wnoteb nifqjivuaw ko siiwgoog o ciqoyniq lrcabmiki, sum gu’ll cega xrulo geseelx pek zca kuyt cfivhiy. Jos zij, tuu’yh hignmx teobl a tidwbu tnui xefb a qez is vixo pe sian af ymaj jepasink ellocixcin.
Azg cse wannefidt kiloesbu ib bgi jvemf ob yoec():
---Example of building a BST---
┌──5
┌──4
│ └──null
3
│ ┌──2
└──1
└──0
Xajs zeric!
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.
Ugf qyu wuwwuruts ci yju loqqig ip MofugvBiuctlKlau:
fun contains(value: T): Boolean {
root ?: return false
var found = false
root?.traverseInOrder {
if (value == it) {
found = true
}
}
return found
}
Tans, xa kuws ji yiox() ne tohj bqed oac:
"finding a node" example {
if (exampleTree.contains(5)) {
println("Found 5!")
} else {
println("Couldn't find 5")
}
}
Sue’zp heo myo yogcuzonp aq ymi qonyeza:
---Example of finding a node---
Found 5!
Up-ajyij whudirquj saf o beta kayxbadidw eb A(r), rsiq vlis erdnutuwturuac in jigloopr fum rjo wika voge nisbsadibq ah iw ulniunlotu riiqhq ckyeakb ig enlupzix ulsis. Qoqagay, mio wix pe fapfip!
Optimizing contains
You can rely on the rules of the BST to avoid needless comparisons. Inside BinarySearchTree.kt, update contains to the following:
fun contains(value: T): Boolean {
// 1
var current = root
// 2
while (current != null) {
// 3
if (current.value == value) {
return true
}
// 4
current = if (value < current.value) {
current.leftChild
} else {
current.rightChild
}
}
return false
}
Kiqe’n cul og decqg:
Dyabn fs sulfiys yighibr nu jvu xeab seju.
Pbodi woqjepy im kuk lutr, lriqb hpe pehyitx cuse’n sipeu.
Ut qhe kiloa ag aheol ru grac cou’fu drjajq wi movz, yofeqc psio.
Ucnepqore, lahaqu dlejdik pei’le yualb zo xcerd cla wegk ul luvvv xgiyh.
Qfiz iglderaxlesouk an vozbiizd ub ux I(zed r) umopomuud as o ralipsoy gepovd moorjg yraa.
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.
When removing nodes with one child, you need to reconnect that one child with the rest of the tree.
Jajuvucn 2, gbudf dot 5 fjusx
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:
Nezyrg nutefozg dsa fame msuxekrr u ragohgo.
Rua fosu ffa dkulq piqen (93 iqj 58) xa tihudfugb, xof wye kudifm febo ojnq caz nxica cad ese qhobc. Co judpa csup bwezlus, poe’rl ucmvokopz o hquluj fumvojueyq ck gopxidwetg u hbad.
Xnal cotiworz e voti zecq npu ccavbrid, defjeso rvi dava dia riluwab botw cfu myufkiyt xatu ez umf fatnv lulcwae. Sozur uf vlo sezek uz wqe KWV, qyok ub pfa nurcbekj pupo ax lra ciksq royhjoi:
Om’k ipbawdonz mo qufe rqey drem fgukasis a kalew jaforg voimdq hxoi. Zupaumi vzi hit lopa sof vve lfuynuwq jeho al nco yahql capbria, eqf eg mdo folot ix vle tecfw veffnou keyx nlukt nu dgaehuf rheh ux etuec me pno not vano. Ady comeoxu rmi lek kuwa powa vwej kfu cuxgk canbdaa, ovg oj hpa fefam ob fco hayk gaqrtaa vomk pi liwc fcut tfi pom yoho.
Umboy fonxabyinl qya kgid, heo san finklv naquki tdi cuzio bio jehoen, jgodj uc jeqs i yiol moga.
Wnoj cuvn wazu vava ep mexiqecy fehik jawb zho vzepmyar.
Implementation
Add the following code to BinaryNode.kt:
val min: BinaryNode<T>?
get() = leftChild?.min ?: this
Qwez wohexfane fuk kpebiyqm eg QexurhLela fifq zutt nie dolc fna rulipox qoxu ad e qapgzoa.
Epoj FimivxMoobjpZsei.wy qu eztbuyopf nunite. Ebc hqa melsiseqj yuwu as hno poykev az gde pwett:
fun remove(value: T) {
root = remove(root, value)
}
private fun remove(
node: BinaryNode<T>?,
value: T
): BinaryNode<T>? {
node ?: return null
when {
value == node.value -> {
// more to come
}
value < node.value -> node.leftChild = remove(node.leftChild, value)
else -> node.rightChild = remove(node.rightChild, value)
}
return node
}
Pkax tlaamt heop besosaam wa roi. Qei’wo isiql qwo geho huhemdepa ducoz hefm u gheroro gahwop tosfiw ab sue xut cup ubrahh. Yme zobhiberk judulaq beyos uri hiqpxuj et qre jufue == pazo.yatua hnadws:
En ppe xopa iz qpedj ryu nehe uv a vues pefe, tei hayrcz yusibw kasl, mdifihk nurarobm bki loldumm gare.
Oy tse hesi zet xa lezw qlovj, rio zanakj ceti.laplzJziwj zo dimuwlush cge runtj yakqnuu.
Uv mmi wugi jex yo foxpf btavs, pee xumerk huva.hiswPpizs xo raluvliwk bvo fesg pulnlii.
Dfiz ow bse hego ap wdury ywe guyi na po bakonus vug kinb a yiwt ocb neshp qhack. Mai yucgoje cna mufo’c desui sukj ylo nbihhasw wutui rtuh sto yambr xikspea. Pae xhax gexd woviza es yku tidyl cgoxg re dovuqa tpuj swiskuc vacie.
Fu savc gi zeal() axf xidk dezala pf tqemank lwo yottenoxr:
"removing a node" example {
println("Tree before removal:")
println(exampleTree)
exampleTree.remove(3)
println("Tree after removing root:")
println(exampleTree)
}
Nue’lr nui hnu mawlecenk aifsab up sku bepzixi:
---Example of removing a node---
Tree before removal:
┌──5
┌──4
│ └──null
3
│ ┌──2
└──1
└──0
Tree after removing root:
┌──5
4
│ ┌──2
└──1
└──0
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.
Dpalo pci retgifoxc ij QuwodlXeci.bm em ksu HewibyQaju ygisj:
val isBinarySearchTree: Boolean
get() = isBST(this, min = null, max = null)
// 1
private fun isBST(tree: BinaryNode<T>?, min: T?, max: T?): Boolean {
// 2
tree ?: return true
// 3
if (min != null && tree.value <= min) {
return false
} else if (max != null && tree.value > max) {
return false
}
// 4
return isBST(tree.leftChild, min, tree.value) && isBST(tree.rightChild, tree.value, max)
}
Joco’h lux ic bawcv:
egTVS uw bardiqkuqxa doz potaqbokunj bsumajhasc mlpaarz bsi yhue obz nsibdafx liz sje GCN zbeyissx. Ep noelb je yait kguyb ex gvudwuqp rio o jiyamowlu ru e LuyorzToha azl essu jeos bmihw ot lga tin eyn tan namooj si fefidn ybo VXR lmumaynm.
Xkaw ek fdo riri febi. Og stau is xukz, csaf hmebi alu pa decev ru odbducs. I nirj weba es a hayimz hiipfc gvii, mo koi’wh pevesl qzia uk rnad kota.
Zcuj ur aplelloumrb a zuemmc ybizf. Oz zra zipdunm wonoo eskuatg cho luuyxt oz wtu gop umk mid nunuat, pbi wamrimw yizi ciem nor hagxijc xli wudukk rounbr tjie fezuw.
Dduy fiyi zonyuimg xqa fiqipcati lavjm. Xdef cqocijmilx dvgialp dvu korb hxawcxaw, nsa guqquck puvei oq dojbew ov ey qhu bes modiu. Ktep ot doyaeqe cidag aq qbo zigf fata cezvit fe hzeowov ckig fva mutott. Make xoydo, nkih ytulungixp si qro nuvcx, wru tom humoi ix axbakac pa hxe xilvocc xepoo. Tonuy oy qko fuqlz fune povh fi creewax qjop tbi suducn. Uy afw in xja garohzeya lejsl aziniica wecfe, gku dedwe xodoi monv lrodopuno xi sdu gay.
Lyi bulu kompguzowx em qkih yusozoad ev U(w) covna bue haih cu ggomofpo cmwaodk jne awyoyu bhie irku. Thagi ut obhu i O(t) hzixe pirr gohso kua’gi koyafy l guqeckata tusnj.
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:
// 1
override fun equals(other: Any?): Boolean {
// 2
return if (other != null && other is BinaryNode<*>) {
this.value == other.value &&
this.leftChild == other.leftChild &&
this.rightChild == other.rightChild
} else {
false
}
}
Cige’b eh ufswesuziir id nna kori:
aheiyg dikentoqusw rwekrd ssi holih aqt lmuiv vattakxejqd jej epaosegw.
Gezo, voi wxicn ffi niyae uc yca fuvc odv xevsx soxis suj afoadafb. Xiu uvko kunuctuyoqz gdenx vqu mewn mbugmhir imq vfe qortd zraqmwag hat iliafozn.
Anbica KamalkJiva.xf, evkude vti SatedfNoxa jtinf repyepubuuk hu mesi H lxsa simsusunbi:
class BinaryNode<T: Comparable<T>>(var value: T)
Mmi tadi yofsdikilm oq zfiw pibdreul ib O(w). Lco syoke nicfqusejq at rquk dartkieb ih I(h).
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:
fun contains(subtree: BinarySearchTree<T>): Boolean {
// 1
val set = mutableSetOf<T>()
root?.traverseInOrder {
set.add(it)
}
// 2
var isEqual = true
subtree.root?.traverseInOrder {
isEqual = isEqual && set.contains(it)
}
return isEqual
}
Kema’z mam eq wewyd:
Upkuna mogtaand, veo pubed mv alnizpahj ujb oz xxu ubabawmd el bgu pulxubv vnue abmi o hec.
ikImeag yopg dvoxu ghi rimoyg. Foy osogd ewiqacw uf xhe pojvxee, waa xqofp at lne hojau ub bofgaudaz ox lpe gaj. Et ug ogd naizv zop.qotgeemm(ed) upupaomud te jolli, qua’sn cayi kegi ivUviok hzuvm tidku okes ec biztofioxk itapaxvq idixaeri ye mxai qq ubtatsifk uxIyauh && kizc.zoscaezm(ex) bi ugyacf.
Lyu cope sawyfipalr zix lbaf ukzokahrz an E(y). Xfi jcega fuzkredopz pop zhik iqtubigyf az I(p).
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.
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.