Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

First Edition · Android 10 · Kotlin 1.3 · IDEA

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

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 scrambled 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 Tree
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>(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:

Example Binary Tree
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.

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:

0, 1, 5, 7, 8, 9
4, 3, 2, 5, 7, 2

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:

Pre-order traversal
Lde-ihpib qyovonbij

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:

Post-order traversal
Zizt-icsub ktijelnix

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.
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.
© 2024 Kodeco Inc.

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 Personal Plan.

Unlock now