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

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)

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

    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.

Algorithm in Scala

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

This solution is available for access!

or

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

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

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

View the rest of Scala algorithms