Scala algorithm: Traverse a tree Depth-First
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!
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
Def Inside Def
A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.
It is also frequently used in combination with Tail Recursion.
The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
A state machine is the use of `sealed trait` to represent all the possible states (and transitions) of a 'machine' in a hierarchical form.