tailrec implementation of tree depth algo

Question

Please advice is there a way to have a tailrec implementation of "classical" tree depth algo.

import scala.annotation.tailrec

object Tree extends App {

  sealed trait Tree[+A]

  case class Node[A](value: A,
                     left: Option[Tree[A]] = None,
                     right: Option[Tree[A]] = None) extends Tree[A]

  object Node:
    def apply[A](value: A) =
      new Node[A](value = value, left = None, right = None)

    def apply[A](value: A, node: Tree[A]) =
      new Node[A](value = value, left = Some(node), right = None)

    def apply[A](value: A, left: Tree[A], right: Tree[A]) =
      new Node[A](value = value, left = Some(left), right = Some(right))

    def unapply[A](node: Node[A]): (A, Option[Tree[A]], Option[Tree[A]]) =
      (node.value, node.left, node.right)

  def go[A](node: Option[Tree[A]]): Int =
    node match
      case None => 0
      case Some(Node(_, left, right)) => Math.max(go(left), go(right)) + 1

  val tree = Node(value = "root",
    left = Node(value = "a"),
    right = Node(value = "b",
      left = Node(value = "c"),
      right = Node(value = "d")))

  println(go(Some(tree)))

}

I've found some pointers to use CPS (continuation passing style) way - but it still fails for me.

Thanks.

Answer 1

There probably wouldn't be a solution for this question which is both tail recursive, efficient and that would work for all possible kind of tree (this is not 100% true, this is probable as far as I could reason about). Let me explain what I mean. In a tail recursive action, returning expression must be either a calculated value or a call to the function itself, with no extra computation on the returning expression/value, right? Think about factorial calculation, you either return the accumulated value, or just call the function itself. Now in your case your tree might look something like this:

        R
      /  \ 
    A     B
   / \   /
  C  D   E
 /
F 

Lets start on R, both children nodes are fulfilled, how do you want to calculate the maximum depth of nodes? You HAVE to traverse the whole depth of both sub trees (A and B) and return the maximum right? so your adding an extra operation on the return value of A and B depths (Math.max). Now there fortunately is an approach to somehow turn the expression to tail recursive, but it is not efficient at all.

...
// in your else expression where you know that the node is not empty itself
(node.left.isEmpty, node.right.isEmpty) match {
  case (true, true) => currentDepth + 1
  case (true, false) => go(node.right, currentDepth)
  case (false, true) => go(node.left, currentDepth)
  case _ =>
    val leftLDepth = go(node.left, currentDepth)
    val rightDepth = go(node.right, currentDepth)
    // this is were everything gets dirty
    if (leftDepth > rightDepth) {
      go(node.left, currentDepth)
    } else if (rightDepth > leftDepth) {
      go(node.right, currentDepth)
    } else { leftLength }
}

This actually is terrible, time complexity of this touches the 7th sky. So you can actually do it with tail recursion , but tail recursion is not suitable for this case. And pay attention that this is not actually tailrec, it just might be accepted by the compiler as tailrec (maybe, not sure!). because when you're calculating the children nodes depth and comparing, you're using 2 stackframes for each of the calculations (each of them can also have 2 childrens, so...).

Dynamic programming seems a better fit.

---

Update

I actually tried to implement the approach, and the compiler does not accept it, since the call to the function, is not only in the tail position :D