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.


import ceylon.collection {
	ArrayList
}
 
shared void run() {
 
	class Node(label, left = null, right = null) {
		shared Integer label;
		shared Node? left;
		shared Node? right;
		string => label.string;
	}
 
	void preorder(Node node) {
		process.write(node.string + " ");
		if(exists left = node.left) {
			preorder(left);
		}
		if(exists right = node.right) {
			preorder(right);
		}
	}
 
	void inorder(Node node) {
		if(exists left = node.left) {
			inorder(left);
		}
		process.write(node.string + " ");
		if(exists right = node.right) {
			inorder(right);
		}
	}
 
	void postorder(Node node) {
		if(exists left = node.left) {
			postorder(left);
		}
		if(exists right = node.right) {
			postorder(right);
		}
		process.write(node.string + " ");
	}
 
	void levelOrder(Node node) {
		value nodes = ArrayList<Node> {node};
		while(exists current = nodes.accept()) {
			process.write(current.string + " ");
			if(exists left = current.left) {
				nodes.offer(left);
			}
			if(exists right = current.right) {
				nodes.offer(right);
			}
		}
	}
 
	value tree = Node {
		label = 1;
		left = Node {
			label = 2;
			left = Node {
				label = 4;
				left = Node {
					label = 7;
				};
			};
			right = Node {
				label = 5;
			};
		};
		right = Node {
			label = 3;
			left = Node {
				label = 6;
				left = Node {
					label = 8;
				};
				right = Node {
					label = 9;
				};
			};
		};
	};
 
	process.write("preorder:   ");
	preorder(tree);
	print("");
	process.write("inorder:    ");
	inorder(tree);
	print("");
	process.write("postorder:  ");
	postorder(tree);
	print("");
	process.write("levelorder: ");
	levelOrder(tree);
	print("");
}