RIC/IT 02/2018

ALGO(T)
	curr=T, last=next=NIL
	ret=1
	a=b=0
	S_T=S_x=NIL

	while (curr != NIL || S_T != NIL) do
		if (curr != NIL) then
			ret=1
			x= curr->key % 2
			push(S_T, curr)
			push(S_x, x)
			next= curr->dx
		else
			curr= top(S_T)
			if (last != curr-> sx && curr->sx != NIL) then
				x= top(S_x)
				pop(S_x)
				a= ret
				x=a+x
				push(S_x, x)
				next= curr->sx
			else
				pop(S_T)
				x= top(S_x)
				pop(S_x)
				if (curr->sx != NIL) then
					y= ret
				else
					y= 1
				ret= x*y*curr->key
				next= NIL
		last=curr
		curr=next
	return ret