BFS and DFS tree traversal
Any comments are welcomed, but I am mostly annoyed by terminalNode


From my opinion, it's more natural to provide default values for case classes:

case class Node[+T](value: T, left: Option[Node[T]] = None, right: Option[Node[T]] = None) {//...


Then you can simply use Node(42) anywhere in your code.


  Node looks like a monad. Could I get all other operations such as flatMap and foldLeft for free somehow?


Typically, any methods in Monads are based on flatMap and unit methods. Therefore you need to implement flatMap method, as unit method you already have (Node.apply).

flatMap needs to accept a method, which returns new instance of Node, e.g. def flatMap[V](f: T =&gt; Node[V]): Node[V]. Then it should look like the following:

def flatMap[V](f: T =&gt; Node[V]): Node[V] = {
    f(value).copy(
      left = left.map(_.flatMap(f)),
      right = right.map(_.flatMap(f))
    )
}


And it you create a new test, it produce the same output, as for map:

println("map: " + tree1.map(i =&gt; s"Hello$i"))
println("fmap: " + tree1.flatMap(i =&gt; Node(s"Hello$i"))) //will be the same outputs


But, you should handle cases, when f(value) may return new node with existing left and/or right values, otherwise the implementation above may override the result. You need to consider this in your final implementation.

Then, according to the rule of map, it can be present as map(f) = fmap unit f, so you can create method map2 with flatMap:

def map2[V](f: T =&gt; V): Node[V] =
  flatMap(t =&gt; Node(f(t)))


Then you will have the same outputs:

println("map: " + tree1.map(i =&gt; s"Hello$i"))
println("map2: " + tree1.map2(i =&gt; s"Hello$i")) //will be the same outputs


Regarding foldLeft: typically you can almost everything implement with foldLeft, but not otherwise. So we need to understand, what foldLeft should do (DSF?), and then we can express other methods with this.

Also couple notes, I'd change (it's arguable, of course, but worth considering):


Instead of left.map(l =&gt; l.map(f) I'd use left.map(_.map(f))
tree.map(t =&gt; (output = t :: output)) this can be replaced with mutable ArrayBuffer for 2 reasons: it should be slightly faster and slightly more well-looking.


Consider this code:

 def dfs2[T](tree: Node[T]): List[T] = {
   val output = ArrayBuffer[T]()
   tree.map(output += _)
   output.toList
 }


And outputs again will be the same:

println("dfs: " + dfs(tree1))
println("dfs2: " + dfs2(tree1)) //will be the same outputs


Hope that helps.