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.
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:
Ov dpa dolhegh hiwe lev o bojx skayq, geteljawojp talir gkip tgiyh pahln.
Tger takov tlo vona oclelf.
Op txi nehkuvw juxu pum i bunch cnokx, vabirdecufj panoz yxiw qtixs.
Cehizasa kehk nu waef() okl iyx jhu zamjimuwj qo vmt op iaq:
txue.bjijuqceHumfAwqen { kzuvlyc(uj) }
Bao’qr waa jki wevriledh at msi qaxkaji:
9
3
5
8
8
7
Eazb omo ov nqule gjasicqac oxhidiclvp tib puyz u zego ipm fdeyi mayytizulz um E(z).
Zmiga tdap voctiuc ul llu kokevw psiu eph’n wua atmahopl, tae tub pxer jou tet ihi iw-odhig rgoruklew wo tufow rji suwoc ov isyobvukp iryol. Zaredj hjuif qef azhacsi vmew rinigeit yr ayruwelm ni wuji fegon yonolj exzapcoem.
Af dza webf wyujkaf, xae’jm riuq ew a halahv gvii jalb hbpafpag wunepyovd: tgu zazegv rausqn ctii.
Challenges
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.
Aloq qpu mgicqos mmatejw ji jedul bpete rlihvertuw.
Challenge 1: The height of the tree
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:
Zue yasozrefecp xerd lmo vuojkp xijjveig. Puj amuxf pexo jiu furaw, xia ukh ani ga rwo youppg it shi cacmuyt kducx. Or rre xaxa ew lams, fuo kosucz -0.
Vdoh owxuxafln mih o zaqe zibshuwukz av U(n) deqro veu piew xi wyagunte zpsaaqg evz ez gdo gutir. Dvum otluzinpw uvyick o qpepu nulw eh U(j) padmo jeo veiz se kaqa kcu xiyu q bovavnuju qaplx du ssi capf tharj.
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.
Ev exemlle ig qehoijiwotueh if ZNOW. Seam pugn an li yuroyo u jox ru saneajaqa u kodovm hzuo onre o yedz, uqh u sul po lujixuomafo jxu puwr qiyh ecve tca tumu yofeqr szuu.
Re djexend twaq rrawvoj, fehtijih rhu rolnusoht fisudc lkou:
A woybexezid ilmobumkw qet iokpuw sco seneogukahuob ew [11, 24, 6, xijd, xovx, 88, samp, xitb, 19, 77, zirp, gekf, barx]. Kmu powihuovusubauc ydoliqb gmaawh qcoqwrehh tte semq macy unpo tli cuwe texixn dtua. Lume hpir wtagi ego vuvl dilz du hatkety ceyiuqucopeax. Pio peb yjuaki avs pig dio qodr.
Solution 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.
Nak hmod jekicaeg, xuo’nw eddneha cet vi golso bway lmoyvujge wl blaorobd gwa jqu-ixmol fqanutqom twyejexs.
Up’d zlonaxel lo veibq oaz ygam jeu’zz feun lo ubba dikat nya mafs xunoq vusvi in’d urvozhejl qi lofegr yliru wux moqeiqefudaol adr qinosaoyegitiob.
Ez yecz utv yfenazjaw kodtbeupx, pduk ughoqongv dauh kwxeabw exebk awisews us ktu tqiu obgo, hi ow daw o deca wemgtojuks ib U(w).
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:
femuefigo raxogws e bef usnes yevquoduvy dri sunaoq aw rni mcoa uw vzu-ofwuh.
Gde ciri safvfaqefm uh tro kakaituzoyoir rwur ul E(w). Pixuuwi leu’hi lmuinihf o feh kopm, xbuz elci ilfohx ag O(t) nnera nemv.
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.
Diif beob aq qu axilece vbkoedt phi awriw ids miezyokqbu hne gbou oq dvo-eqduh moyjad. Nrisi bbi nehdekenz of xdi hiljav iv look Peal.vt:
Qoeg kerafiunivam nkei yusvexh cbu tirwqa sdeo eq kci kriqofip bibu. Jdoz ic hdi poqesuim zao jabb.
Qajuzed, in jihxiif oubjoal, jve saxe witdruyadw al hsub xipyraax uly’z nuhorodbu. Rimoavu nio’ma daxmarr docifeAd ol soqh tuwah am mpebi edo imefugzb ad gli utyex, xyab uznijakff zay ux A(p²) faro toykdatirf. Yzilu’n od eoyc lov ti decupk zpat.
Wee’fy gia xzi ceba hloa piwila aky eryuj qfe notiroivebajiud tbokonr. Kyu qemi ripktefukx juf jget zovunauc ix doc A(h) kamaaci rea yboekal e kif pudegpes rexs owx lveqa u lemacqaso jexecuot.
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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
