## Data Structures & Algorithms in Kotlin

1 min

#### Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters

#### Section II: Elementary Data Structures

Section 2: 3 chapters

#### Section IV: Sorting Algorithms

Section 4: 5 chapters

# 7. Binary Trees Written by Irina Galata

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 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:

### 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.

``````override fun toString() = diagram(this)

private fun diagram(node: BinaryNode<T>?,
top: String = "",
root: String = "",
bottom: String = ""): String {
return node?.let {
if (node.leftChild == null && node.rightChild == null) {
"\$root\${node.value}\n"
} else {
diagram(node.rightChild, "\$top ", "\$top┌──", "\$top│ ") +
root + "\${node.value}\n" + diagram(node.leftChild, "\$bottom│ ", "\$bottom└──", "\$bottom ")
}
} ?: "\${root}null\n"
}
``````
``````println(tree)
``````
`````` ┌──null
┌──9
│ └──8
7
│ ┌──5
└──1
└──0
``````

## 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:

``````fun traverseInOrder(visit: Visitor<T>) {
leftChild?.traverseInOrder(visit)
visit(value)
rightChild?.traverseInOrder(visit)
}
``````
``````tree.traverseInOrder { println(it) }
``````
``````0
1
5
7
8
9
``````

### Pre-order traversal

Pre-order traversal visits the nodes of a binary tree in the following order:

``````fun traversePreOrder(visit: Visitor<T>) {
visit(value)
leftChild?.traversePreOrder(visit)
rightChild?.traversePreOrder(visit)
}
``````
``````tree.traversePreOrder { println(it) }
``````
``````7
1
0
5
9
8
``````

### Post-order traversal

Post-order traversal always visits the nodes of a binary tree in the following order:

``````fun traversePostOrder(visit: Visitor<T>) {
leftChild?.traversePostOrder(visit)
rightChild?.traversePostOrder(visit)
visit(value)
}
``````
``````tree.traversePostOrder { println(it) }
``````
``````0
5
1
8
9
7
``````

## 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.

### 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:

``````fun height(node: BinaryNode<T>? = this): Int {
return node?.let { 1 + max(height(node.leftChild),
height(node.rightChild)) } ?: -1
}
``````

### 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.

#### 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.

#### Traversal

Write the following code to BinaryNode.kt:

``````fun traversePreOrderWithNull(visit: Visitor<T>) {
visit(value)
leftChild?.traversePreOrderWithNull(visit) ?: visit(null)
rightChild?.traversePreOrderWithNull(visit) ?: visit(null)
}
``````

#### 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?>()
return list
}
``````

#### 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.

``````fun deserialize(list: MutableList<T?>): BinaryNode<T?>? {
// 1
val rootValue = list.removeAt(list.size - 1) ?: return null

// 2
val root = BinaryNode<T?>(rootValue)

root.leftChild = deserialize(list)
root.rightChild = deserialize(list)

return root
}
``````
``````println(tree)
val array = tree.serialize()
println(tree.deserialize(array))
``````
``````┌──null
┌──9
│ └──8
7
│ ┌──5
└──1
└──0

┌──null
┌──9
│ └──8
7
│ ┌──5
└──1
└──0
``````
``````fun deserializeOptimized(list: MutableList<T?>): BinaryNode<T>? {
return deserialize(list.asReversed())
}
``````
``````val rootValue = list.removeAt(list.size - 1) ?: return null
``````
``````println(tree.deserializeOptimized(array))
``````

## 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.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.