Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


class Node{ var [mixin=Node]left,right; var v;
   fcn init(val,[Node]l=Void,[Node]r=Void) { v,left,right=vm.arglist }
}
 
class BTree{ var [mixin=Node] root;
   fcn init(r){ root=r }
   const VISIT=Void, LEFT="left", RIGHT="right";
   fcn preOrder  { traverse(VISIT,LEFT, RIGHT) }
   fcn inOrder   { traverse(LEFT, VISIT,RIGHT) }
   fcn postOrder { traverse(LEFT, RIGHT,VISIT) }
   fcn [private] traverse(order){  //--> list of Nodes
      sink:=List();
      fcn(sink,[Node]n,order){
         if(n){ foreach o in (order){
	    if(VISIT==o) sink.write(n);
	    else self.fcn(sink,n.setVar(o),order);  // actually get var, eg n.left
	 }}
      }(sink,root,vm.arglist);
      sink
   }
   fcn levelOrder{  // breadth first
      sink:=List(); q:=List(root);
      while(q){
         n:=q.pop(0); l:=n.left; r:=n.right;
	 sink.write(n);
	 if(l) q.append(l);
	 if(r) q.append(r);
      }
      sink
   }
}