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
    

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"
)

Algorithm in Scala

32 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!

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

1. 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('-')
   }
   
   assert(exampleDef("test") == "-test-")
   

   ▶ Run code in the IDE

   It is also frequently used in combination with Tail Recursion.

2. 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').

3. 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")
   

   ▶ Run code in the IDE

4. State machine

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