Traverse a tree Depth-First with purely-functional immutable Scala

Algorithm goal

Traversing a tree means going through every element through a tree - a structure diagrammed below and also in the test-cases.

There are two key traversal types: Depth-First (this one) and Breadth-first (TraverseTreeBreadthFirst). Depth-first means you go as far down the tree as possible first, whereas breadth-first you go as wide as possible (in the diagram below, 3rd item would be E, in breadth-first search).

The goal is to extract the tree labels in depth-first fashion, thus giving us a list 'A', 'B', 'C', 'D', 'E', 'F', 'G'.

graph TD
A[A - 1st item]
B[B - 2nd item]
C[C - 3rd item]
D[D - 4th item]
E[E - 5th item]
F[F - 6th item]
G[G - 7th item]
A --> B
A --> E
B --> C
B --> D
E --> F
E --> G
    

Explanation

In the traversal, the key thing is using the List structure of Scala as a 'Stack', So that as soon as we reach a branch, we can push its children to the top of the stack, meaning that we will go to the children (depth-first) first.

Once an item has been covered, we will dequeue it (by deconstructing it with a Pattern Matching). When all are traversed, we are done. (this is © from www.scala-algorithms.com)

Also please see: TraverseTreeBreadthFirst.

Scala Concepts & Hints

State machine

A state machine is the use of `sealed trait` to represent all the possible states of a 'machine' in a hierarchical form

Read more

Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

Read more

Def Inside Def

A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.

def exampleDef(input: String): String = {
  def surroundInputWith(char: Char): String = s"$char$input$char"
  surroundInputWith('-')
}
Lazy List

The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').

Read more

Algorithm in Scala

33 lines of Scala (version 2.13), showing how concise Scala can be!

This solution is available for purchase!

'Unlimited Scala Algorithms' gives you access to all solutions!

Upon purchase, you will be able to Register an account to access solutions on multiple devices.

Test cases in Scala

assert(
  traverseTree(sampleTree)(Tree.children).map(_.label).toList ==
    List("A", "B", "C", "D", "E", "F", "G"),
  "Labels are fetched in depth-first order"
)
def traverseTree[T](t: T)(getChildren: T => List[T]): LazyList[T] = ???