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

6. Trees
Written by Irina Galata, Kelvin Lau and Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... 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.

Unlock now

A tree
A tree

The tree is a data structure of profound importance. It’s used to tackle many recurring challenges in software development, such as:

  • Representing hierarchical relationships.
  • Managing sorted data.
  • Facilitating fast lookup operations.

There are many types of trees, and they come in various shapes and sizes. In this chapter, you’ll learn the basics of using and implementing a tree.

Terminology

There are many terms associated with trees, so it makes sense to get familiar with a few of them before starting.

Node

Like the linked list, trees are made up of nodes.

Node
Qalu

Parent and child

Trees are viewed starting from the top and branching toward the bottom — just like a real tree, only upside-down.

Parent and child
Qotifb upw nyinl

Root

The topmost node in the tree is called the root of the tree. It’s the only node that has no parent:

Root
Wuoq

Leaf

A node that has no children is called a leaf:

Leaf
Hiun

Implementation

To get started, open the starter project for this chapter.

class TreeNode<T>(val value: T) {
  private val children: MutableList<TreeNode<T>> = mutableListOf()
}
fun add(child: TreeNode<T>) = children.add(child)
fun main() {
  val hot = TreeNode("Hot")
  val cold = TreeNode("Cold")

  val beverages = TreeNode("Beverages").run {
    add(hot)
    add(cold)
  }
}
A small tree
A ccact ysuu

Traversal algorithms

Iterating through linear collections such as arrays or lists is straightforward. Linear collections have a clear start and end:

Traversing arrays or lists
Nkoxagnams erqitm in befxw

Traversing trees
Bpihepyuck hvaej

typealias Visitor<T> = (TreeNode<T>) -> Unit

Depth-first traversal

Depth-first traversal starts at the root node and explores the tree as far as possible along each branch before reaching a leaf and then backtracking.

fun forEachDepthFirst(visit: Visitor<T>) {
  visit(this)
  children.forEach {
    it.forEachDepthFirst(visit)
  }
}
fun makeBeverageTree(): TreeNode<String> {
  val tree = TreeNode("Beverages")

  val hot = TreeNode("hot")
  val cold = TreeNode("cold")

  val tea = TreeNode("tea")
  val coffee = TreeNode("coffee")
  val chocolate = TreeNode("cocoa")

  val blackTea = TreeNode("black")
  val greenTea = TreeNode("green")
  val chaiTea = TreeNode("chai")

  val soda = TreeNode("soda")
  val milk = TreeNode("milk")

  val gingerAle = TreeNode("ginger ale")
  val bitterLemon = TreeNode("bitter lemon")

  tree.add(hot)
  tree.add(cold)

  hot.add(tea)
  hot.add(coffee)
  hot.add(chocolate)

  cold.add(soda)
  cold.add(milk)

  tea.add(blackTea)
  tea.add(greenTea)
  tea.add(chaiTea)

  soda.add(gingerAle)
  soda.add(bitterLemon)

  return tree
}
A big tree
I xur njao

fun main() {
  val tree = makeBeverageTree()
  tree.forEachDepthFirst { println(it.value) }
}
Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

Level-order traversal

Level-order traversal is a technique that visits each node of the tree based on the depth of the nodes. Starting at the root, every node on a level is visited before going to a lower level.

fun forEachLevelOrder(visit: Visitor<T>) {
  visit(this)
  val queue = Queue<TreeNode<T>>()
  children.forEach { queue.enqueue(it) }

  var node = queue.dequeue()
  while (node != null) {
    visit(node)
    node.children.forEach { queue.enqueue(it) }
    node = queue.dequeue()
  }
}
Level-order traversal
Masor-uppec zluluzlec

fun main() {
  val tree = makeBeverageTree()
  tree.forEachLevelOrder { println(it.value) }
}
beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon

Search

You already have a method that iterates through the nodes, so building a search algorithm won’t take long.

fun search(value: T): TreeNode<T>? {
  var result: TreeNode<T>? = null

  forEachLevelOrder {
    if (it.value == value) {
      result = it
    }
  }

  return result
}
fun main() {
  val tree = makeBeverageTree()
  tree.search("ginger ale")?.let {
    println("Found node: ${it.value}")
  }

  tree.search("WKD Blue")?.let {
    println(it.value)
  } ?: println("Couldn't find WKD Blue")
}
Found node: ginger ale
Couldn't find WKD Blue

Challenges

Challenge 1: Tree challenge

Print the values in a tree in an order based on their level. Nodes belonging to the same level should be printed on the same line. For example, consider the following tree:

15
1 17 20
1 5 0 2 5 7

Solution 1

A straightforward way to print the nodes in level-order is to leverage the level-order traversal using a Queue data structure. The tricky bit is determining when a newline should occur.

fun printEachLevel() {
  // 1
  val queue = ArrayListQueue<TreeNode<T>>()
  var nodesLeftInCurrentLevel = 0

  queue.enqueue(this)
  // 2
  while (queue.isEmpty.not()) {
    // 3
    nodesLeftInCurrentLevel = queue.count

    // 4
    while (nodesLeftInCurrentLevel > 0) {
      val node = queue.dequeue()
      node?.let {
        print("${node.value} ")
        node.children.forEach { queue.enqueue(it) }
        nodesLeftInCurrentLevel--
      } ?: break
    }

    // 5
    println()
  }
}

Key points

  • Trees share some similarities to linked lists. However, a tree node can link to infinitely many nodes, whereas linked-list nodes may only link to one other node.
  • Get comfortable with the tree terminology such as parent, child, leaf and root. Many of these terms are common and are used to help explain other tree structures.
  • Traversals, such as depth-first and level-order traversals, aren’t specific to only the general type of tree. They work on other types of trees as well, although their implementation is slightly different based on how the tree is structured.
  • Trees are a fundamental data structure with different implementations. Some of these will be part of the next chapters.
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 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.

Unlock now