constant_stack.scala

def preOrderR[T,S](tree: Tree[T], f: T => S): Queue[S] = {
  def loop(stack: List[Tree[T]], output: Queue[S]): Queue[S] = stack match {
    case Nil => output
    case Tree(v,c)::ts => loop(c:::ts,output.enqueue(f(v)))
  }
  loop(tree::Nil, Queue.empty)
}

def postOrderR[T,S](tree: Tree[T], f: T => S): Queue[S] = {
  def loop(stack: List[Tree[T]], output: Queue[S]): Queue[S] = stack match {
    case Nil => output
    case Tree(v,Nil)::ts => loop(ts,output.enqueue(f(v)))
    case Tree(v,c::cs)::ts => loop(c::Tree(v,cs)::ts, output)
  }
  loop(tree::Nil,Queue.empty)
}