Tail recursive functions for BinaryTree

Question

I am stuck with implementing tail recursive foreach, reduce, map and toList functions for a very simple implementation of binary tree.

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {

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

  def foreach[A](tree: Tree[A], f: (A) => Unit): Unit = {
    //@tailrec
    def iter[A](tree: Tree[A], f: (A) => Unit): Unit = tree match {
      case EmptyTree =>
      case Node(v, l, r) =>
        iter(l, f)
        f(v)
        iter(r, f)
    }
    iter(tree, f)
  }

  def reduce[A](tree: Tree[A], value: A, f: (A, A) => A): A = {
    //@tailrec
    def loop(tree: Tree[A], value: A): A = tree match {
      case Node(v, l, r) => loop(l, f(loop(r, value), v))
      case EmptyTree => value
    }
    loop(tree, value)
  }

  def map[A, B](tree: Tree[A], f: A => B): Tree[B] = {
    //@tailrec
    def iter[A](tree: Tree[A], f: A => B): Tree[B] = tree match {
      case Node(v, l, r) => Node(f(v), iter(l, f), iter(r, f))
      case EmptyTree => EmptyTree
    }
    iter(tree, f)
  }

  def toList[A](t: Tree[A]): List[A] = {
    //@tailrec
    def iter[A](t: Tree[A]): List[A] = t match {
      case Node(v, l, r) => v :: iter(l) ::: iter(r)
      case EmptyTree => List.empty
    }
    iter(t)
  }
}

Code for testing:

val tree = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, Tree(6), Tree(7)))
Tree.foreach(tree, (x: Int) => println(x))
Tree.reduce(tree, 0, (x: Int, y: Int) => x + y)
Tree.map(tree, (x: Int) => x + 1)
Tree.toList(tree)

I cant use @tailrec attribute because as you can see, recursive calls are not the last calls in a function, and I do not know how to rewrite it because there are several calls in one function, for example

v :: iter(l) ::: iter(r)

I know that I can use accumulator for inner recursive functions but how I should use it in case of several calls ?

Thanks in advance.

Updated:

def toListRec[A](tree: Tree[A]): List[A] = {
  @tailrec
  def iter(result: List[A], todo: List[Tree[A]]): List[A] = todo match {
    case x :: tail => x match {
      case Node(v, l, r) => iter(v :: result, l :: r :: tail)
      case EmptyTree => iter(result, tail)
    }
    case Nil => result.reverse
  }
  iter(List.empty, List(tree))
}

Tree processing is not naturally tail-recursive: you can't make recursion "the last thing" in your method, because after recursing the first subtree, there's still one subtree (or more, if it's not a binary tree) left to process. So, you need to manually re-implement what a compiler would do: either a call stack or continuations, and use that as the accumulator. A linked list is kind of a degenerate tree, with one subtree per node, that's why there's such a simple 1:1 mapping from the list structure to a tail-recursive call-graph structure. — Jörg W Mittag
– Jörg W Mittag, Commented Aug 13, 2016 at 9:24

mweerden · Accepted Answer · 2016-08-13 13:20:01Z

10

Without tail recursion, a(/the) stack is used to keep track of calling functions. If you want to use tail recursion, you'll have to find a way to keep track of this information elsewhere. In simpler "linear" cases, such as factorial, this information is pretty limited and can often easily be taken care of by using an accumulator.

In your case, the problem is that the recursion isn't linear. After one recursive call, the function doesn't just compute the result, but it makes another recursive call before being able to get to the result.

In order to apply tail recursion in this case, you will have to explicitly keep track of the remaining recursive calls that have to be made. An easy way is to simply keep a "to-do" list. For example:

def toList[A](t: Tree[A]): List[A] = {
  @tailrec def iter[A](todo: List[Tree[A]], r: List[A]): List[A] =
  todo match {
    case t :: rest => t match {
      case Node(v, l, r) => iter(l :: r :: rest,  v :: r)
      case EmptyTree => iter(rest, r)
    }
    case List.empty => reverse(r)
  }
  iter(List(t), List.empty)
}

Disclaimer: I know nothing about scala. :)

edited Aug 13, 2016 at 13:20

answered Aug 13, 2016 at 9:34

mweerden

14.1k5 gold badges35 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Victor Moroz Over a year ago

case EmptyTree => iter(m, r) => case EmptyTree => iter(rest, r)?

anch Over a year ago

@mweerden Thank you ! You guys are best. And actually your scala is pretty good too )))

gevmart · Accepted Answer · 2017-09-02 19:00:45Z

-3

The solution that mweerden suggests would work, however, there is another way of solving the problem, which I think is much more elegant. Here is the code which traverses a tree to list

def toList[T](t: Tree[T]): List[T] = {
  def tailRecursive(tree: Tree[T], acc: List[T]): List[T] = tree match {
    case EmptyTree => acc
    case Node(value, right, left) => 
      tailRecursive(left, value :: tailRecursive(right, acc))
  }
  tailRecursive(t, List())
}

The solution implies that the tree is a binary search tree, and the list produced will be in ascending order (if the ascending order is not required, 6th line can be changed, putting the value in front of first recursive call or straightly into the accumulator would be possible).

edited Sep 2, 2017 at 19:00

answered Sep 2, 2017 at 13:51

gevmart

11 bronze badge

1 Comment

TRuhland Over a year ago

tailRecursive is not tail recursive

Collectives™ on Stack Overflow

Tail recursive functions for BinaryTree

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related