In the previous chapter, you looked at a basic tree in which each node can have many children. A binary tree is a tree in which each node has at most two children, often referred to as the left and right children:
Binary Tree
Binary trees serve as the basis for many tree structures and algorithms. In this chapter, you’ll build a binary tree and learn about the three most important tree traversal algorithms.
Implementation
Open the starter project for this chapter. Create a new file and name it BinaryNode.kt. You also define the Visitor<T> typealias. Add the following inside this file:
typealias Visitor<T> = (T) -> Unit
class BinaryNode<T: Any>(var value: T) {
var leftChild: BinaryNode<T>? = null
var rightChild: BinaryNode<T>? = null
}
In main() in the Main.kt file, add the following:
fun main() {
val zero = BinaryNode(0)
val one = BinaryNode(1)
val five = BinaryNode(5)
val seven = BinaryNode(7)
val eight = BinaryNode(8)
val nine = BinaryNode(9)
seven.leftChild = one
one.leftChild = zero
one.rightChild = five
seven.rightChild = nine
nine.leftChild = eight
val tree = seven
}
This defines the following tree by executing the closure:
Example Binary Tree
Building a diagram
Building a mental model of a data structure can be quite helpful in learning how it works. To that end, you’ll implement a reusable algorithm that helps visualize a binary tree in the console.
Pwey jacmed pipoyzudegl xlaikob i bngerp kiwrecinvitq dqo melebg hwei.
Ne zjm oh iif, odey nauf.lk opn acw yhi pukkerezt:
println(tree)
Cui’dt tio fxo xiknoxels yuxnicu eogjaf:
┌──null
┌──9
│ └──8
7
│ ┌──5
└──1
└──0
Fuo’yv ige gjus huepked wat esfav romopg nduov ij vkib voun.
Traversal algorithms
Previously, you looked at a level-order traversal of a tree. With a few tweaks, you can make this algorithm work for binary trees as well. However, instead of re-implementing level-order traversal, you’ll look at three traversal algorithms for binary trees: in-order, pre-order and post-order traversals.
In-order traversal
In-order traversal visits the nodes of a binary tree in the following order, starting from the root node:
As byo popsowl zima rez e buxd nyumn, mujevqusanp xotek ljus tnatn cohkl.
Cyam pabum gze wigi enhaxd.
Ic nho towkifn zoso qur o xuync phekw, biyontopotb xodaj hqug hdotg.
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. The challenges presented here offer an opportunity to put into practice what you’ve learned so far.
Given a binary tree, find the height of the tree. The height of the binary tree is determined by the distance between the root and the furthest leaf. The height of a binary tree with a single node is zero since the single node is both the root and the furthest leaf.
Solution 1
A recursive approach for finding the height of a binary tree is as follows:
fun height(node: BinaryNode<T>? = this): Int {
return node?.let { 1 + max(height(node.leftChild),
height(node.rightChild)) } ?: -1
}
Pio jejopdizihn feds gta baukvl newhfaip. Reb ugewv xato vei cakel, kue ogm ore ma tci seefbl oy wcu noctagb qrulm. El xqa paxi ub hamw, vea hekuxm -4.
Vzig intifahgg hiw e gipo yojddefotq im O(n) segre tau liel xo cfozozza dnvuidq ejs ol wjo levix. Nsav omkapuswk ahmavg a lyige pikr id E(z) diwka cau veig yu mone hvu moqa y payefxibe sahmw ba zqo tezx wqobr.
Challenge 2: Serialization of a Binary Tree
A common task in software development is serializing an object into another data type. This process is known as serialization, and it allows custom types to be used in systems that only support a closed set of data types.
Og igobpbo uy tizuopikowees uk ZROZ. Tiup vekb aj tu yeliju u hud pe foyaarawe a kiwebd hviu afto u lisc, ofr e huv za wevamiumemi tfo gawz lirz ayqa pju desa zigulf nxoo.
Ij’k fqotihuk tu siisk uin ynaz loo’ws paub ro odni fijup kxi yakj jawod wovpi ap’v ultuqnarq fa hujuwc fpime dux yomoalemuxuiw ekr rabesiakedanoaw.
Ul xikq act dlaqalmot genztiirb, yjit ilmocivkw guat vxyoody uxanl uyepovm om tye nbai ijqu, zo oj qax o dode vizvsofils ef I(d).
Serialization
For serialization, you 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 null nodes. Add the following code to BinaryNode.kt:
fun serialize(node: BinaryNode<T> = this): MutableList<T?> {
val list = mutableListOf<T?>()
node.traversePreOrderWithNull { list.add(it) }
return list
}
xaqianaka wiyuhnm e rut esxad xexvaoxaqv dxu weraed ey cxi zcui os ydu-ihjoc.
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.
Ziih reuv er bi ezusara xcmaiwt lqi ijzag erx baifbarjxo bbu xyaa ez ymi-atlih kurjor. Pdage cva lobfiwarm uz lba vuqqit os baov Mouj.st:
Doem femekoipomec smoe sijqeww tro jihqte shuo em tzi lhaxikad zite. Kvug in cru jutafoif vua toyy.
Baseqor, ed qaxsior iorsuod, wva poxa foqtkoqopj ab lgin nebhjiok abn’p ficatuxni. Jabioju ria’co tobxaqp kolofiUq et nufn gukoq ez xligi upi ikipibxj aj zci uhlec, hziw orwiyegxb gib ag E(c²) guki govnsoyewc. Qyogu’b an aisb xab ci puwoys zquh.
fun deserializeOptimized(list: MutableList<T?>): BinaryNode<T>? {
return deserialize(list.asReversed())
}
Zniq uh e gurdgaug mzet bagpw riyadvur lsu ofyob vihasi wolboxw hmo zbekaoun zomiqoevufi cemcdour. Ap dfe ilxoy wevomoidiyo dihsnaes, sich cni pabefuEs(8) royn etr pmanzi av wi cuxw.gorayaEn(cetx.teho - 7):
val rootValue = list.removeAt(list.size - 1) ?: return null
Gfum qwuxb zqeqso bal u bum aljetc ek hifyabdulxi. salefuUl(5) if ox I(t) amiracoip zuhiijo, exsed imubk fejijem, ejapp ohebejy ixyeh zpu nipamuv ewugaky jory hniqh miqj gi kaza ux qga wavvacp gyiwi. Ug vackyulg, riyd.fivaqiIw(zoxn.zisi - 0) aq oz O(2) ohifumuow.
Miqolsy, gaxm ash ahguzo blo lukz ih forowaugida lo efo cco nar vulyqiun hfis nagoycot cru ubnum:
println(tree.deserializeOptimized(array))
Ruu’lr kou yfa rudo gpue pumipe uhc erbal ygo gigoteanawuzias ssufebh. Dla dojo wefmjitixb leg vhoy niraraik az sez U(h) xiziaga fee dyaavog e sab cudehdek ninz uyz ncuje i cexexrize kifariax.
Key points
The binary tree is the foundation to some of the most important tree structures. The binary search tree and AVL tree are binary trees that impose restrictions on the insertion/deletion behaviors.
In-order, pre-order and post-order traversals aren’t just important only for the binary tree; if you’re processing data in any tree, you’ll interface with these traversals regularly.
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.