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

## 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

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


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

## Algorithm in Scala

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

## 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] = ???