public abstract class TreeWalk {
	public static <T> void breadthFirst(BinaryTree<T> tree, TreeCursor<T> start, Operation<? super T> op) {
		Queue<TreeCursor<T>> q = new LinkedQueue<TreeCursor<T>>();
		q.enqueue(start);
		while (q.size() > 0) {
			TreeCursor<T> current = q.dequeue();
			TreeCursor<T> next = tree.toLeft(current);
			if (next != null) {
				q.enqueue(next);
			}
			next = tree.toRight(current);
			if (next != null) {
				q.enqueue(next);
			}
			op.performOn(tree.getElement(current));
		}
	}
	
	public static <T> void inOrder(BinaryTree<T> tree, TreeCursor<T> start, Operation<? super T> op) {
		if (start != null) {
			inOrder(tree, tree.toLeft(start), op);
			op.performOn(tree.getElement(start));
			inOrder(tree, tree.toRight(start), op);
		}
	}

	public static <T> void preOrder(BinaryTree<T> tree, TreeCursor<T> start, Operation<? super T> op) {
		if (start != null) {
			op.performOn(tree.getElement(start));
			preOrder(tree, tree.toLeft(start), op);
			preOrder(tree, tree.toRight(start), op);
		}
	}

	public static <T> void postOrder(BinaryTree<T> tree, TreeCursor<T> start, Operation<? super T> op) {
		if (start != null) {
			postOrder(tree, tree.toLeft(start), op);
			postOrder(tree, tree.toRight(start), op);
			op.performOn(tree.getElement(start));
		}
	}
	
	public static void main(String [] args) {
		class TreePrinter implements Operation<String> {

			@Override
			public void performOn(String item) {
				System.out.print(item + " ");
			}
		}
		BinaryTree<String> t = new LinkedBinaryTree<String>(
						           new LinkedBinaryTree<String>(
						               new LinkedBinaryTree<String>("2"), "*", new LinkedBinaryTree<String>("x")
						           ),
						           "+",
						           new LinkedBinaryTree<String>("3")
							   );
		System.out.println(t.toString());
		TreePrinter print = new TreePrinter();
		System.out.print("Breadth-first walk: ");
		breadthFirst(t, t.root(), print);
		System.out.println();
		
		System.out.print("In order walk: ");
		inOrder(t, t.root(), print);
		System.out.println();
		
		System.out.print("Pre-order walk: ");
		preOrder(t, t.root(), print);
		System.out.println();
		
		System.out.print("Post-order walk: ");
		postOrder(t, t.root(), print);
	}

}