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

Problem

Solution

This solution is available for purchase!

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

We use Stripe for secure payment processing.


Alternatively, get unlimited solutions for $3.99 per month!

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

Test cases

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

Scala Concepts

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('-')
}
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")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

Pattern matching is used by methods like Collect, but can also be easily integrated into normal functions.

Pattern matches are effectively "Partial Functions", of type PartialFunction[Input, Output] which is isomorphic to Input => Option[Output]. See Option Type.

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 using a List (aka. a Stack).
  • 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)

Also please see: TraverseTreeDepthFirst.