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.


oo::class create tree {
    # Basic tree data structure stuff...
    variable val l r
    constructor {value {left {}} {right {}}} {
	set val $value
	set l $left
	set r $right
    }
    method value {} {return $val}
    method left  {} {return $l}
    method right {} {return $r}
    destructor {
	if {$l ne ""} {$l destroy}
	if {$r ne ""} {$r destroy}
    }
 
    # Traversal methods
    method preorder {varName script {level 0}} {
	upvar [incr level] $varName var
	set var $val
	uplevel $level $script
	if {$l ne ""} {$l preorder $varName $script $level}
	if {$r ne ""} {$r preorder $varName $script $level}
    }
    method inorder {varName script {level 0}} {
	upvar [incr level] $varName var
	if {$l ne ""} {$l inorder $varName $script $level}
	set var $val
	uplevel $level $script
	if {$r ne ""} {$r inorder $varName $script $level}
    }
    method postorder {varName script {level 0}} {
	upvar [incr level] $varName var
	if {$l ne ""} {$l postorder $varName $script $level}
	if {$r ne ""} {$r postorder $varName $script $level}
	set var $val
	uplevel $level $script
    }
    method levelorder {varName script} {
	upvar 1 $varName var
	set nodes [list [self]]; # A queue of nodes to process
	while {[llength $nodes] > 0} {
	    set nodes [lassign $nodes n]
	    set var [$n value]
	    uplevel 1 $script
	    if {[$n left] ne ""} {lappend nodes [$n left]}
	    if {[$n right] ne ""} {lappend nodes [$n right]}
	}
    }
}