Task 2.2)

(Assuming that t.left and t.right will return subtrees because: t is represented by the root node, thus making t.left and t.right subtrees and therefor also nodes)

void printTreeListNodes(t : tree)
{
	// Check if recursive algorithm has reach the ned
	if(t == NIL)
	{
		return
	}

	// Check if current node is a list node
	if(isListNode(t))
	{
		print(t.key)
	}

	// Do recursive calls
	printTreeListNodes(t.left)
	printTreeListNodes(t.right)
}

boolean isListNode(x : node)
{
	// Check if x have 1 child
	if(x.left && !x.right || !x.left && x.right)
	{
		// Check if child is a leaf
		if(x.left.left || x.left.right || x.right.left || x.right.right)
		{
			return true
		}
	}
	return false
}

Worst case running time of printTreeListNodes will be Θ(n) because isListNode is Θ(1). 
printTreeListNodes will visit all nodes only once.


Task 2.3)

root, size findLargetsListFreeTree(t : tree)
{
	if(t == NIL)
	{
		return (NIL, 0)
	}

	// Test if root is a list free tree
	if(isListFree(t))
	{
		return (sizeof(t), t)
	}

	// Do recursive calls
	left = findLargetsListFreeTree(t.left)
	right = findLargetsListFreeTree(t.right)

	// Return the largest
	if(findLargetsListFreeTree(t.left).size > findLargetsListFreeTree(t.right))
	{
		return left
	}
	else
	{
		return right
	}
}

boolean isListFree(t : tree)
{
	// Check if current node is list node
	if(isListNode(t))
	{
		return false
	}

	// Recursive calls
	if(isListFree(t.left) == false || isListFree(t.right) == false)
	{
		return false
	}

	return true
}