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.


sub preorder
{
	my $t = shift or return ();
	return ($t->[0], preorder($t->[1]), preorder($t->[2]));
}
 
sub inorder
{
	my $t = shift or return ();
	return (inorder($t->[1]), $t->[0], inorder($t->[2]));
}
 
sub postorder
{
	my $t = shift or return ();
	return (postorder($t->[1]), postorder($t->[2]), $t->[0]);
}
 
sub depth
{
	my @ret;
	my @a = ($_[0]);
	while (@a) {
		my $v = shift @a or next;
		push @ret, $v->[0];
		push @a, @{$v}[1,2];
	}
	return @ret;
}
 
my $x = [1,[2,[4,[7]],[5]],[3,[6,[8],[9]]]];
 
print "pre:   @{[preorder($x)]}\n";
print "in:    @{[inorder($x)]}\n";
print "post:  @{[postorder($x)]}\n";
print "depth: @{[depth($x)]}\n";