dholbrook · June 21, 2012 17:59 · Jul 1, 2012 · Jun 28, 2012 · Jun 21, 2012 · Jun 21, 2012
diff --git a/Tree.scala b/Tree.scala
@@ -1,16 +1,24 @@
+/**
+ * D Holbrook
+ *
+ * Code Club: PO1
+ *
+ * (*) Define a binary tree data structure and related fundamental operations.
+ *
+ * Use whichever language features are the best fit (this will depend on the language you have selected).  The following operations should be supported:
+ *
+ *    Constructors
+ *        (bitree data left right) - Should return a binary tree containing data and the left and right children.
+ *    Accessors
+ *        (bitree-data t) - Should return the data contained by the tree.
+ *        (bitree-left t) - Should return the left child of the tree.
+ *        (bitree-right t) - Should return the right child of the tree.
+ *    Predicates
+ *        (bitree-leaf? t) - Should return true if the tree is a leaf (has null left and right children), false otherwise
+ */
 trait Tree[+A] {
 
-  private implicit def preorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
-    fold(n.r, fold(n.l, f(z, n.v))(f)(preorder))(f)(preorder)
-  }
-
-  private def inorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
-    fold(n.r, f(fold(n.l, z)(f)(inorder), n.v))(f)(inorder)
-  }
-
-  private def postorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
-    f(fold(n.r, fold(n.l, z)(f)(postorder))(f)(postorder), n.v)
-  }
+  import scala.annotation.tailrec
 
   def value: Option[A] = this match {
     case n: Node[A] => Some(n.v)
@@ -30,16 +38,187 @@ trait Tree[+A] {
     case Empty      => None
   }
 
-  def fold[B](z: B)(f: (B, A) => B): B = {
-    fold(this, z)(f)
+  /**
+   * Represents a deferred evaluation of a node value
+   */
+  private case class Eval[A](v: A) extends Tree[A]
+
+  /**
+   * represents common functionality of all traversal order folds
+   */
+  @tailrec
+  private def foldLoop[A, B](a: List[Tree[A]], z: B)(f: (B, A) => B)(o: (Node[A], List[Tree[A]]) => List[Tree[A]]): B = a match {
+    case (n: Node[A]) :: tl => foldLoop(o(n, tl), z)(f)(o) // never directly evaluate nodes, function o will create new accumulator
+    case (l: Leaf[A]) :: tl => foldLoop(tl, f(z, l.v))(f)(o) // always evaluate Leaf 
+    case (e: Eval[A]) :: tl => foldLoop(tl, f(z, e.v))(f)(o) // always evaluate Eval 
+    case Empty :: tl        => foldLoop(tl, z)(f)(o) // ignore Empty
+    case _                  => z // will be Nil (empty list)
   }
 
-  private def fold[A, B](t: Tree[A], z: B)(f: (B, A) => B)(implicit o: (Node[A], B, (B, A) => B) => B): B = t match {
-    case l: Leaf[A] => f(z, l.v)
-    case n: Node[A] => o(n, z, f)
-    case _          => z
+  /**
+   * fold with preorder traversal (root, left, right)
+   * Tail Recursive Optimized
+   *
+   *        F
+   *      /   \
+   *    B       G
+   *   / \       \
+   *  A   D       I
+   *     / \     /
+   *    C   E   H
+   *
+   * head evaluate accumulator
+   * ---- -------- -----------
+   *              | (F)
+   * F   | ()     | F::B::G::()
+   * F   | (F)    | (B,G)
+   * B   | ()     | B::A::D::(G)
+   * B   | (B)    | (A,D,G)
+   * A   | (A)    | (D,G)
+   * D   | ()     | D::C::E::(G)
+   * D   | (D)    | (C,E,G)
+   * C   | (C)    | (E,G)
+   * E   | (E)    | (G)
+   * G   | ()     | G::I::()
+   * G   | (G)    | (I)
+   * I   | ()     | I::H::()
+   * I   | (I)    | (H)
+   * H   | (H)    | ()
+   *
+   * result
+   * F, B, A, D, C, E, G, I, H
+   */
+  def foldPreorder[B](z: B)(f: (B, A) => B): B = {
+    foldLoop(List(this), z)(f) { (n, tl) => Eval(n.v) :: n.l :: n.r :: tl }
   }
 
+  /**
+   * fold with inorder traversal (left, root, right)
+   * tail recursive optimized
+   *
+   *        F
+   *      /   \
+   *    B       G
+   *   / \       \
+   *  A   D       I
+   *     / \     /
+   *    C   E   H
+   *
+   * head evaluate accumulator
+   * ---- -------- -----------
+   *              | (F)
+   * F   | ()     | B::F::G::()
+   * B   | ()     | A::B::D::(F,G)
+   * A   | (A)    | (B,D,F,G)
+   * B   | (B)    | (D,F,G)
+   * D   | ()     | C::D::E::(F,G)
+   * C   | (C)    | (D,E,F,G)
+   * D   | (D)    | (E,F,G)
+   * E   | (E)    | (F,G)
+   * F   | (F)    | (G)
+   * G   | ()     | G::I::()
+   * G   | (G)    | (I)
+   * I   | ()     | H::I::()
+   * H   | (H)    | H
+   * I   | (I)    | ()
+   *
+   * result
+   * A,B,C,D,E,F,G,H,I
+   */
+  def foldInorder[B](z: B)(f: (B, A) => B): B = {
+    foldLoop(List(this), z)(f) { (n, tl) => n.l :: Eval(n.v) :: n.r :: tl }
+  }
+
+  /**
+   * fold with postorder traversal (left, right, root)
+   * tail recursive optimized
+   *
+   *        F
+   *      /   \
+   *    B       G
+   *   / \       \
+   *  A   D       I
+   *     / \     /
+   *    C   E   H
+   *
+   * head evaluate accumulator
+   * ---- -------- -----------
+   *              | (F)
+   * F   | ()     | B::G::F::()
+   * B   | ()     | A::D::(B,G,F)
+   * A   | (A)    | (D,B,G,F)
+   * D   | ()     | C::E::D::(B,G,F)
+   * C   | (C)    | (E,D,B,G,F)
+   * E   | (E)    | (D,B,G,F)
+   * D   | (D)    | (B,G,F)
+   * B   | (B)    | (G,F)
+   * G   | ()     | I::G::(F)
+   * I   | ()     | H::I::(G,F)
+   * H   | (H)    | (I,G,F)
+   * I   | (I)    | (G,F)
+   * G   | (G)    | (F)
+   * F   | (F)    | ()
+   *
+   * result
+   * A,C,E,D,B,H,I,G,F
+   */
+  def foldPostorder[B](z: B)(f: (B, A) => B): B = {
+    foldLoop(List(this), z)(f) { (n, tl) => n.l :: n.r :: Eval(n.v) :: tl }
+  }
+
+  /**
+   * fold with levelorder traversal
+   * tail recursive optimized
+   *
+   *        F
+   *      /   \
+   *    B       G
+   *   / \       \
+   *  A   D       I
+   *     / \     /
+   *    C   E   H
+   *
+   * head evaluate accumulator
+   * ---- -------- -----------
+   *              | (F)
+   * F   | ()     | (F::()) ::: (B,G)
+   * F   | (F)    | (B,G)
+   * B   | ()     | (B::(G)) ::: (A,D)
+   * B   | (B)    | (G,A,D)
+   * G   | ()     | (G::(A,D)) ::: (I)
+   * G   | (G)    | (A,D,I)
+   * A   | (A)    | (D,I)
+   * D   | ()     | (D::(I)) ::: (C,E)
+   * D   | (D)    | (I,C,E)
+   * I   | ()     | (I::(C,E)) ::: (H)
+   * I   | (I)    | (C,E,H)
+   * C   | (C)    | (E,H)
+   * E   | (E)    | (H)
+   * H   | (H)    | ()
+   *
+   * result
+   * F, B, G, A, D, I, C, E, H
+   */
+  def foldLevelorder[B](z: B)(f: (B, A) => B): B = {
+    foldLoop(List(this), z)(f) { (n, tl) => (Eval(n.v) :: tl) ::: List(n.l, n.r) }
+  }
+
+  /**
+   * calls foldInorder
+   */
+  def fold[B](z: B)(f: (B, A) => B): B = foldInorder(z)(f)
+
+  /**
+   * P02
+   * (*) Count the number of nodes in a binary tree.
+   */
+  def size: Int = fold(0) { (sum, v) => sum + 1 }
+
+  /**
+   * P03
+   * (*) Determine the height of a binary tree.
+   * Definition:  The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.
+   */
   def height: Int = {
     def loop(t: Tree[A]): Int = t match {
       case l: Leaf[A] => 1
@@ -49,41 +228,67 @@ trait Tree[+A] {
     loop(this) - 1
   }
 
+  /**
+   * P04
+   * (*) Count the number of leaves in a binary tree.
+   */
   def leafCount: Int = {
-    def loop(t: Tree[A]): Int = t match {
-      case l: Leaf[A] => 1
-      case n: Node[A] => Seq(loop(n.left.get), loop(n.right.get)).sum
-      case _          => 0
+    @tailrec
+    def loop(t: List[Tree[A]], z: Int): Int = t match {
+      case (l: Leaf[A]) :: tl => loop(tl, z + 1)
+      case (n: Node[A]) :: tl => loop(n.left.get :: n.right.get :: tl, z)
+      case _ :: tl            => loop(tl, z)
+      case _                  => z
     }
-    loop(this)
+    loop(List(this), 0)
   }
 
-  def size: Int = fold(0) { (sum, v) => sum + 1 }
-
-  def toSeq: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l } reverse
+  def toSeq: Seq[A] = fold(List[A]()) { (l, v) => v :: l } reverse
 
-  def toSeqPreorder: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l }(preorder) reverse
+  def toSeqPreorder: Seq[A] = foldPreorder(List[A]()) { (l, v) => v :: l } reverse
+  def toSeqInorder: Seq[A] = foldInorder(List[A]()) { (l, v) => v :: l } reverse
+  def toSeqPostorder: Seq[A] = foldPostorder(List[A]()) { (l, v) => v :: l } reverse
+  def toSeqLevelorder: Seq[A] = foldLevelorder(List[A]()) { (l, v) => v :: l } reverse
 
-  def toSeqInorder: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l }(inorder) reverse
-
-  def toSeqPostorder: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l }(postorder) reverse
-
+  /**
+   * P05
+   * (**) Find the last element in a binary tree using pre/in/post/level order traversals.
+   *  Note:  This is S-99 problem P01 converted from lists to binary trees.
+   */
   def lastPreorder = toSeqPreorder.last
-
   def lastInorder = toSeqInorder.last
-
   def lastPostorder = toSeqPostorder.last
+  def lastLevelorder = toSeqLevelorder.last
 
+  /**
+   * P06
+   * (**) Find the last but one element in a binary tree using pre/in/post/level order traversals.
+   *  Note:  This is S-99 problem P02 converted from lists to binary trees.
+   */
   def penultimatePreorder = toSeqPreorder.dropRight(1).last
-
+  def penultimateInorder = toSeqInorder.dropRight(1).last
+  def penultimatePostorder = toSeqPostorder.dropRight(1).last
+  def penultimateLevelorder = toSeqLevelorder.dropRight(1).last
+
+  /**
+   * P07
+   * (**) Find the Nth element in a binary tree using pre/in/post/level order traversals.
+   * By convention, the first element in the tree is element 0.
+   *
+   */
+  def nthPreorder(n: Int) = toSeqPreorder(n)
+  def nthInorder(n: Int) = toSeqInorder(n)
+  def nthPostorder(n: Int) = toSeqPostorder(n)
+  def nthLevelorder(n: Int) = toSeqLevelorder(n)
+
 }
 
 case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
 case class Leaf[A](v: A) extends Tree[A]
 case object Empty extends Tree[Nothing]
 
 object Run extends App {
-  val t: Tree[Symbol] = Node('A, Node('B, Leaf('D), Leaf('E)), Node('C, Empty, Node('F, Leaf('G), Empty)))
+  val t: Tree[Symbol] = Node('F, Node('B, Leaf('A), Node('D, Leaf('C), Leaf('E))), Node('G, Empty, Node('I, Leaf('H), Empty)))
   println("tree: " + t)
 
   //print the value of b node navigating from root
@@ -95,55 +300,69 @@ object Run extends App {
   //print the value of e node navigating from root
   for {
     b <- t.left
-    e <- b.right
-    value <- e.value
-  } println("E node: " + value)
+    d <- b.right
+    value <- d.value
+  } println("D node: " + value)
 
   //no println() is executed for empty node chain
   for {
     b <- t.left
-    e <- b.right
-    x <- e.right //no node here
+    d <- b.right
+    e <- d.right
+    x <- e.right
     value <- x.value
   } println("X node SHOUL NOT PRINT!: " + value)
 
+  println("as seq: " + t.toSeq)
+
   println("count: " + t.size)
-  assert(t.size == 7)
+  assert(t.size == 9)
 
   println("height: " + t.height)
   assert(t.height == 3)
 
   println("leaft count: " + t.leafCount)
-  assert(t.leafCount == 3)
+  assert(t.leafCount == 4)
 
-  println("as seq: " + t.toSeq)
+  println("as seqPreorder: " + t.toSeqPreorder)
+  println("as seqInorder: " + t.toSeqInorder)
+  println("as seqPostorder: " + t.toSeqPostorder)
+  println("as seqLevelorder: " + t.toSeqLevelorder)
 
   println("last preorder :" + t.lastPreorder)
-  assert(t.lastPreorder == 'G)
-
   println("last inorder :" + t.lastInorder)
-  assert(t.lastInorder == 'F)
-
   println("last postorder :" + t.lastPostorder)
-  assert(t.lastPostorder == 'A)  
-
-  println("penultimate preorder :" + t.penultimatePreorder)  
-
+  println("last levelorder: " + t.lastLevelorder)
+
+  println("nth preorder 5 : " + t.nthPreorder(5))
+  println("nth inorder 5 : " + t.nthInorder(5))
+  println("nth postorder 5 : " + t.nthPostorder(5))
+  println("nth levelorder 5 : " + t.nthLevelorder(5))
+
+  //    
   /**
    * **** output *********
    *
-    tree: Node('A,Node('B,Leaf('D),Leaf('E)),Node('C,Empty,Node('F,Leaf('G),Empty)))
-    B node: 'B
-    E node: 'E
-    count: 7
-    height: 3
-    leaft count: 3
-    as seq: List('A, 'B, 'D, 'E, 'C, 'F, 'G)
-    last preorder :'G
-    last inorder :'F
-    last postorder :'A
-    penultimate preorder :'F
-
+   * tree: Node('F,Node('B,Leaf('A),Node('D,Leaf('C),Leaf('E))),Node('G,Empty,Node('I,Leaf('H),Empty)))
+   * B node: 'B
+   * D node: 'D
+   * as seq: List('A, 'B, 'C, 'D, 'E, 'F, 'G, 'H, 'I)
+   * count: 9
+   * height: 3
+   * leaft count: 4
+   * as seqPreorder: List('F, 'B, 'A, 'D, 'C, 'E, 'G, 'I, 'H)
+   * as seqInorder: List('A, 'B, 'C, 'D, 'E, 'F, 'G, 'H, 'I)
+   * as seqPostorder: List('A, 'C, 'E, 'D, 'B, 'H, 'I, 'G, 'F)
+   * as seqLevelorder: List('F, 'B, 'G, 'A, 'D, 'I, 'C, 'E, 'H)
+   * last preorder :'H
+   * last inorder :'I
+   * last postorder :'F
+   * last levelorder: List('F, 'B, 'G, 'A, 'D, 'I, 'C, 'E, 'H)
+   * nth preorder 5 : 'C
+   * nth inorder 5 : 'E
+   * nth postorder 5 : 'B
+   * nth levelorder 5 : 'D
+   *
    * ***********************
    */
 

diff --git a/Tree.scala b/Tree.scala
@@ -1,44 +1,89 @@
+trait Tree[+A] {
+
+  private implicit def preorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
+    fold(n.r, fold(n.l, f(z, n.v))(f)(preorder))(f)(preorder)
+  }
+
+  private def inorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
+    fold(n.r, f(fold(n.l, z)(f)(inorder), n.v))(f)(inorder)
+  }
+
+  private def postorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
+    f(fold(n.r, fold(n.l, z)(f)(postorder))(f)(postorder), n.v)
+  }
 
-abstract class Tree[+A] {
   def value: Option[A] = this match {
     case n: Node[A] => Some(n.v)
     case l: Leaf[A] => Some(l.v)
     case Empty      => None
   }
+
   def left: Option[Tree[A]] = this match {
     case n: Node[A] => Some(n.l)
     case l: Leaf[A] => None
     case Empty      => None
   }
+
   def right: Option[Tree[A]] = this match {
     case n: Node[A] => Some(n.r)
     case l: Leaf[A] => None
     case Empty      => None
   }
-  def count: Int = {
-    def loop(t: Tree[_]): Int = t match {
-      case n: Node[_] => Seq(loop(n.left.get), loop(n.right.get)).sum + 1
-      case l: Leaf[_] => 1
-      case Empty      => 0
-    }
-    loop(this)
+
+  def fold[B](z: B)(f: (B, A) => B): B = {
+    fold(this, z)(f)
+  }
+
+  private def fold[A, B](t: Tree[A], z: B)(f: (B, A) => B)(implicit o: (Node[A], B, (B, A) => B) => B): B = t match {
+    case l: Leaf[A] => f(z, l.v)
+    case n: Node[A] => o(n, z, f)
+    case _          => z
   }
+
   def height: Int = {
-    def loop(t: Tree[_]): Int = t match {
-      case n: Node[_] => Seq(loop(n.left.get), loop(n.right.get)).max + 1
-      case l: Leaf[_] => 1
-      case Empty      => 0
+    def loop(t: Tree[A]): Int = t match {
+      case l: Leaf[A] => 1
+      case n: Node[A] => Seq(loop(n.left.get), loop(n.right.get)).max + 1
+      case _          => 0
     }
     loop(this) - 1
-  }  
+  }
+
+  def leafCount: Int = {
+    def loop(t: Tree[A]): Int = t match {
+      case l: Leaf[A] => 1
+      case n: Node[A] => Seq(loop(n.left.get), loop(n.right.get)).sum
+      case _          => 0
+    }
+    loop(this)
+  }
+
+  def size: Int = fold(0) { (sum, v) => sum + 1 }
+
+  def toSeq: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l } reverse
+
+  def toSeqPreorder: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l }(preorder) reverse
+
+  def toSeqInorder: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l }(inorder) reverse
+
+  def toSeqPostorder: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l }(postorder) reverse
+
+  def lastPreorder = toSeqPreorder.last
+
+  def lastInorder = toSeqInorder.last
+
+  def lastPostorder = toSeqPostorder.last
+
+  def penultimatePreorder = toSeqPreorder.dropRight(1).last
+
 }
-case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree
-case class Leaf[A](v: A) extends Tree
+
+case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
+case class Leaf[A](v: A) extends Tree[A]
 case object Empty extends Tree[Nothing]
 
 object Run extends App {
   val t: Tree[Symbol] = Node('A, Node('B, Leaf('D), Leaf('E)), Node('C, Empty, Node('F, Leaf('G), Empty)))
-
   println("tree: " + t)
 
   //print the value of b node navigating from root
@@ -58,24 +103,48 @@ object Run extends App {
   for {
     b <- t.left
     e <- b.right
-    x <- e.right  //no node here
+    x <- e.right //no node here
     value <- x.value
   } println("X node SHOUL NOT PRINT!: " + value)
+
+  println("count: " + t.size)
+  assert(t.size == 7)
+
+  println("height: " + t.height)
+  assert(t.height == 3)
+
+  println("leaft count: " + t.leafCount)
+  assert(t.leafCount == 3)
+
+  println("as seq: " + t.toSeq)
+
+  println("last preorder :" + t.lastPreorder)
+  assert(t.lastPreorder == 'G)
+
+  println("last inorder :" + t.lastInorder)
+  assert(t.lastInorder == 'F)
 
+  println("last postorder :" + t.lastPostorder)
+  assert(t.lastPostorder == 'A)  
 
-  println("count: "  + t.count)
-
-  println("height: "  + t.height)
-
-
-/****** output *********
+  println("penultimate preorder :" + t.penultimatePreorder)  
+
+  /**
+   * **** output *********
+   *
+    tree: Node('A,Node('B,Leaf('D),Leaf('E)),Node('C,Empty,Node('F,Leaf('G),Empty)))
+    B node: 'B
+    E node: 'E
+    count: 7
+    height: 3
+    leaft count: 3
+    as seq: List('A, 'B, 'D, 'E, 'C, 'F, 'G)
+    last preorder :'G
+    last inorder :'F
+    last postorder :'A
+    penultimate preorder :'F
 
-tree: Node('A,Node('B,Leaf('D),Leaf('E)),Node('C,Empty,Node('F,Leaf('G),Empty)))
-B node: 'B
-E node: 'E
-count: 7
-height: 3
+   * ***********************
+   */
 
-*************************/
-
 }
diff --git a/Tree.scala b/Tree.scala
@@ -23,6 +23,14 @@ abstract class Tree[+A] {
     }
     loop(this)
   }
+  def height: Int = {
+    def loop(t: Tree[_]): Int = t match {
+      case n: Node[_] => Seq(loop(n.left.get), loop(n.right.get)).max + 1
+      case l: Leaf[_] => 1
+      case Empty      => 0
+    }
+    loop(this) - 1
+  }  
 }
 case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree
 case class Leaf[A](v: A) extends Tree
@@ -55,11 +63,19 @@ object Run extends App {
   } println("X node SHOUL NOT PRINT!: " + value)
 
 
-  println("count "  + t.count)
+  println("count: "  + t.count)
+
+  println("height: "  + t.height)
+
+
 /****** output *********
+
 tree: Node('A,Node('B,Leaf('D),Leaf('E)),Node('C,Empty,Node('F,Leaf('G),Empty)))
 B node: 'B
 E node: 'E
-count 7
+count: 7
+height: 3
+
 *************************/
+
 }
diff --git a/Tree.scala b/Tree.scala
@@ -1,4 +1,3 @@
-package scalaninetynine
 
 abstract class Tree[+A] {
   def value: Option[A] = this match {

diff --git a/Tree.scala b/Tree.scala
@@ -0,0 +1,66 @@
+package scalaninetynine
+
+abstract class Tree[+A] {
+  def value: Option[A] = this match {
+    case n: Node[A] => Some(n.v)
+    case l: Leaf[A] => Some(l.v)
+    case Empty      => None
+  }
+  def left: Option[Tree[A]] = this match {
+    case n: Node[A] => Some(n.l)
+    case l: Leaf[A] => None
+    case Empty      => None
+  }
+  def right: Option[Tree[A]] = this match {
+    case n: Node[A] => Some(n.r)
+    case l: Leaf[A] => None
+    case Empty      => None
+  }
+  def count: Int = {
+    def loop(t: Tree[_]): Int = t match {
+      case n: Node[_] => Seq(loop(n.left.get), loop(n.right.get)).sum + 1
+      case l: Leaf[_] => 1
+      case Empty      => 0
+    }
+    loop(this)
+  }
+}
+case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree
+case class Leaf[A](v: A) extends Tree
+case object Empty extends Tree[Nothing]
+
+object Run extends App {
+  val t: Tree[Symbol] = Node('A, Node('B, Leaf('D), Leaf('E)), Node('C, Empty, Node('F, Leaf('G), Empty)))
+
+  println("tree: " + t)
+
+  //print the value of b node navigating from root
+  for {
+    b <- t.left
+    value <- b.value
+  } println("B node: " + value)
+
+  //print the value of e node navigating from root
+  for {
+    b <- t.left
+    e <- b.right
+    value <- e.value
+  } println("E node: " + value)
+
+  //no println() is executed for empty node chain
+  for {
+    b <- t.left
+    e <- b.right
+    x <- e.right  //no node here
+    value <- x.value
+  } println("X node SHOUL NOT PRINT!: " + value)
+
+
+  println("count "  + t.count)
+/****** output *********
+tree: Node('A,Node('B,Leaf('D),Leaf('E)),Node('C,Empty,Node('F,Leaf('G),Empty)))
+B node: 'B
+E node: 'E
+count 7
+*************************/
+}