title: Tail recursive fold on a binary tree in Scala
body: <p>I am trying to find a tail recursive fold function for a binary tree. Given the following definitions:</p>
  
  <pre><code>// From the book "Functional Programming in Scala", page 45
  sealed trait Tree[+A]
  case class Leaf[A](value: A) extends Tree[A]
  case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
  </code></pre>
  
  <p>Implementing a non tail recursive function is quite straightforward:</p>
  
  <pre><code>def fold[A, B](t: Tree[A])(map: A =&gt; B)(red: (B, B) =&gt; B): B =
    t match {
      case Leaf(v)      =&gt; map(v)
      case Branch(l, r) =&gt; 
        red(fold(l)(map)(red), fold(r)(map)(red))
    }
  </code></pre>
  
  <p>But now I am struggling to find a tail recursive fold function so that the annotation <code>@annotation.tailrec</code> can be used.</p>
  
  <p>During my research I have found several examples where tail recursive functions on a tree can e.g. compute the sum of all leafs using an own stack which is then basically a <code>List[Tree[Int]]</code>. But as far as I understand in this case it only works for the additions because it is not important whether you first evaluate the left or the right hand side of the operator. But for a generalised fold it is quite relevant. To show my intension here are some example trees:</p>
  
  <pre><code>val leafs = Branch(Leaf(1), Leaf(2))
  val left = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
  val right = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
  val bal = Branch(Branch(Leaf(1), Leaf(2)), Branch(Leaf(3), Leaf(4)))
  val cmb = Branch(right, Branch(bal, Branch(leafs, left)))
  val trees = List(leafs, left, right, bal, cmb)
  </code></pre>
  
  <p>Based on those trees I want to create a deep copy with the given fold method like:</p>
  
  <pre><code>val oldNewPairs = 
    trees.map(t =&gt; (t, fold(t)(Leaf(_): Tree[Int])(Branch(_, _))))
  </code></pre>
  
  <p>And then proof that the condition of equality holds for all created copies:</p>
  
  <pre><code>val conditionHolds = oldNewPairs.forall(p =&gt; {
    if (p._1 == p._2) true
    else {
      println(s"Original:\n${p._1}\nNew:\n${p._2}")
      false
    }
  })
  println("Condition holds: " + conditionHolds)
  </code></pre>
  
  <p>Could someone give me some pointers, please?</p>
  
  <p>You can find the code used in this question at ScalaFiddle: <a href="https://scalafiddle.io/sf/eSKJyp2/15" rel="noreferrer">https://scalafiddle.io/sf/eSKJyp2/15</a></p>