program puuesimerkki2;

uses tra;

procedure print_path(T : TREE; x : ELEMENT);
var	D : DEQUE (* of TREE_NODE *);
	n : TREE_NODE;
	loytyi : boolean;
begin
	VOIDPTR_DEQUE_CREATE(D); 
	loytyi := false;
	if TREE_ROOT(T) <> TREE_NIL then
		VOIDPTR_DEQUE_ENQUEUE(D, top, TREE_ROOT(T));
	while not VOIDPTR_DEQUE_EMPTY(D) and not loytyi do begin
		n := VOIDPTR_DEQUE_FRONT(D);
		if TREE_SAME(T, TREE_RETRIEVE(T, n), x) then
			loytyi := true
		else if TREE_LEFTMOST_CHILD(T, n) <> TREE_NIL then
			VOIDPTR_DEQUE_ENQUEUE(D, top, TREE_LEFTMOST_CHILD(T, n))
		else begin
			while (not VOIDPTR_DEQUE_EMPTY(D)) and (TREE_RIGHT_SIBLING(T, VOIDPTR_DEQUE_FRONT(D)) = TREE_NIL) do
				VOIDPTR_DEQUE_DEQUEUE(D, top);
			if not VOIDPTR_DEQUE_EMPTY(D) then begin
				n := VOIDPTR_DEQUE_FRONT(D);
				VOIDPTR_DEQUE_DEQUEUE(D, top);
				VOIDPTR_DEQUE_ENQUEUE(D, top, TREE_RIGHT_SIBLING(T, n));
			end
		end
	end;

	if (loytyi) then begin
		write('Polku solmuun ');
		TREE_PRINT_NODE(T, VOIDPTR_DEQUE_FRONT(D));
		write(' :');
	end;
	while not VOIDPTR_DEQUE_EMPTY(D) do begin
		write(' ');
		TREE_PRINT_NODE(T, VOIDPTR_DEQUE_REAR(D));
		VOIDPTR_DEQUE_DEQUEUE(D, bottom);
	end;
	writeln;
end;


var puu : TREE;
	n, m, l, k : TREE_NODE;
	x : ELEMENT;
	i : integer;

begin

	(*
             1
           //\\
          /|  |\
         / |  | \
        2  3  4  5
       /\  |  |
      6  7 8  9
              |
              10
	*)

	INT_TREE_CREATE(puu);

	n := INT_TREE_CREATE_NODE(1);
	INT_TREE_ASSIGN_ROOT(puu, n);
	m := INT_TREE_CREATE_NODE(2);
	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, n, m);
	for i := 3 to 5 do begin
		l := INT_TREE_CREATE_NODE(i);
		INT_TREE_ASSIGN_RIGHT_SIBLING(puu, m, l);
		m := l;
	end;

	m := TREE_LEFTMOST_CHILD(puu, TREE_ROOT(puu));
	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(6));
	INT_TREE_ASSIGN_RIGHT_SIBLING(puu, TREE_LEFTMOST_CHILD(puu, m), INT_TREE_CREATE_NODE(7));

	m := TREE_RIGHT_SIBLING(puu, m);
  	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(8));

	m := TREE_RIGHT_SIBLING(puu, m);
	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(9));

	m := TREE_LEFTMOST_CHILD(puu, m);

	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(10));


	(* preorder_print(puu, TREE_ROOT(puu)); *)

	for i := 1 to 10 do
		print_path(puu, INT_ELEMENT(i));

	TREE_FREE(puu);

end.