# Scala algorithm: Traverse a tree Breadth-First, immutably

## Algorithm goal

A Tree data structure is not so simple to process especially if done so recursively - as recursion can lead to a 'Stack overflow error'.

There is a way in Scala to traverse a tree without overflowing the stack, using its LazyList (in Scala 2.12, it's called Stream)

## Test cases in Scala

``````assert(
traverseTree(sampleTree)(Tree.children).map(_.label).toList ==
List("A", "B", "E", "C", "D", "F", "G"),
"Labels are fetched in breadth-first order"
)
``````

## Algorithm in Scala

37 lines of Scala (compatible versions 2.13 & 3.0).

## Explanation

Things to note in this solution:

• A 'sealed trait' and companion-object pair is used to define a Tree. A 'sealed trait' is a structure in Scala that lets you model Algebraic Data Types
• The tree traversal uses an immutable approach. Many traversals use mutable methods, such as 'marking' nodes as visited, but in this case, we use a completely different approach of enqueuing nodes.
• The solution looks recursive, but in fact the use of 'LazyList' of Scala (previously 'Stream' in Scala 2.12), which performs a lazy evaluation. This means that no evaluation is done until requested. This allows us to represent an algorithm in a recursive fashion, without a 'StackOverflowError'
• This could also be rewritten into a tail-recursive function as well as an iteration, but the issue with that would be that we would have to pass a function to the traverser, thus taking control away from the caller. In the LazyList approach, we can actually do things like terminate the stream early (when the desired node is found, for example)

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

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

# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

### Study our 89 Scala Algorithms: 6 fully free, 89 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 21 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Register now (free)

Register with GitHub

## How the algorithms look

1. A description/goal of the algorithm.
2. An explanation with both Scala and logical parts.
3. A proof or a derivation, where appropriate.
4. Links to Scala concepts used in this specific algorithm, also unit-tested.
5. An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
6. Unit tests, with a button to run them immediately in our in-browser IDE.