sumew

<?xml version='1.0' encoding='UTF-8'?><VAST xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" version="2.0" xsi:noNamespaceSchemaLocation="vast.xsd"><Ad id="2660361"><InLine><AdSystem version="1.0">Yahoo Ad Manager Plus</AdSystem><AdTitle>VAST 2.0 Linear Ad</AdTitle><Description>VAST 2.0 Linear Ad</Description><Error><![CDATA[http://pr.ybp.yahoo.com/vasterror/imp/DOE4OOpqPnb2E-cDSvCbr0iff2NF5HVpe33__mLddCrvq-tSYMU-6ly99ha--Sfa2PC10lS0jqVMGdwWdOw0qoAZq3ogSVu4bFuN-pYW_fLdu77mB9nUaLC1a6l6zc0taXM_1eVXnvxKsHm9MkPXCnjIX4eYZCqsrSavoIouoiJycayNPVssYpsFrxM8EhNfeQNikbzxmaEri8_f_uG7B2zibVbe5bUvvdYIPgoHg0ScjQWddSxveGyW7jhZxLpmN_lGBAu7VeJmeBcgK55h4oG1BaPUl47Ina4O9t4hITjPGqcfgQQ0w8Z9asTCT4Uhm1CrNf11r2X50ogh3pTi4Ejsr0B3LfqxdH7vdeVFjFYGGI7J-3VqWOESVAqu9wE-5YnDNpr_7ASbyhGmzmI3zCbhBAByPqYVJBkDftNjp6kTgjm9ugMwEaFjnzlmzgJbUALLZ5U9B63_PcnhfhK_6XZFu5c-LfyFbl_YwlErPvb3HKv6f61kHteak-pEEv66ryP89iPJNwYU21eHKzMe3fI8T0M0x-bmlS7lA9vrTtogCEulmW1X2PBxR2DosDQt32pqEnrDsrs4NtC6j-0l6KFI9nA6FqJ14CPg8ot_nX_UM5dQklIikQE42_OacPxxlATt9mN-nDXdhQ

sumew

 case class Tree[T](value: T, children: List[Tree[T]])

  /**
   *
   * @param tree
   * @param f A function to be applied to every node in the tree
   * @tparam S Output type
   * @tparam T Value type of node
   * @return A Queue[S] where the first element is the output of first node visited
   *

sumew

/**  
  *               1
  *             / |  \
  *           /   |   \
  *         /     |    \
  *        2      3     8
  *      /  \    / \   / \
  *     4    5  6   7 9  10
  * Preorder:  1,2,4,5,3,6,7,8,9,10
  * PostOrder: 4,5,2,6,7,3,9,10,8,1

sumew

def preOrder[T,S](tree: Tree[T], f: T => S): Queue[S] = {
  def loop(g: Tree[T], output: Queue[S]): Queue[S] = g match {
    case Tree(v,c) =>   c.foldLeft(output.enqueue(f(v))){case (acc,n) => loop(n,acc)}
  }
  loop(tree,Queue.empty[S])
}

sumew

def foldLeft[B](z: B)(op: (B, A) => B): B

sumew

def postOrder[T,S](tree: Tree[T], f: T => S): Queue[S] = {
  def loop(g: Tree[T], output: Queue[S]): Queue[S] = g match {
    case Tree(v,rest) => rest.foldLeft(output){case (agg,node) => loop(node,agg)}.enqueue(f(v))
  }
  loop(tree,Queue.empty)
}

sumew

def inOrder[T,S](tree: Tree[T], f: T => S): Queue[S] = {
  def loop(g: Tree[T], output: Queue[S]): Queue[S] = g match {
    case Tree(v,l::ls) => ls.foldLeft(loop(l,output).enqueue(f(v))){case (acc,n) => loop(n,acc)}
    case Tree(v,Nil) => output.enqueue(f(v))
  }
  loop(tree, Queue.empty)
}

sumew

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 {

sumew

  case class BTree[T](value: T, left: Option[BTree[T]], right: Option[BTree[T]])

sumew

/**
  * At each step, enqueue the value at the current node and add 
  * the left & right children to the stack. Option's toList 
  * helps convert empty children (None values) to an empty list
  */
def preOrderC[T, S](root: Option[BTree[T]], f: T => S): Queue[S] = {
  def loop(stack: List[BTree[T]], acc: Queue[S]): Queue[S] = stack match {
    case Nil => acc
    case BTree(v, l, r) :: ts => loop(l.toList ::: r.toList ::: ts, acc.enqueue(f(v)))
  }