// Iterative insertion for binary search tree.
// Note: this a code fragment, it cannot be compiled directly.

TreeNode<T> insertItem(TreeNode<T> n, T newItem)
// returns a reference to the new root of subtree rooted in n
{
	TreeNode<T> newNode = new TreeNode<T>)newItem);
	if (n == null)
		return newNode;
	
	// search for the insertion position
	TreeNode<T> prev = null;
	TreeNode<T> cur = n;
	while (cur!=null) {
		prev=cur;
		if (newItem.getKey() < cur.getItem().getKey())
			cur = cur.getLeft();
		else
			cur = cur.getRight();
	}
	
	// insert newNode as a child of prev
	if (newItem.getKey() < prev.getItem().getKey())
		prev.getLeft(newNode);
	else
		prev.setRight(newNode);
	
	// the root didn't change
	return n;
}  // end insertItem