7.
Binary Trees
Written by Irina Galata, Kelvin Lau and Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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>(val 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?>()
node.traversePreOrderWithNull { list.add(it) }
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.