insertNodeHelper operation (Tree)

[Emerald214]

I don't understand why **ptr is used in this code. Please expain to me.

template<class NODETYPE>
void Tree<NODETYPE>::insertNode(const NODETYPE &value)
{	insertNodeHelper(&rootPtr, value);	}

template<class NODETYPE>
void Tree<NODETYPE>::insertNodeHelper(TreeNode<NODETYPE> **ptr, const NODETYPE &value)
{
	if(*ptr == 0)
		*ptr = new TreeNode<NODETYPE>(value);
	else
	{
		if(value < (*ptr)->data)
			insertNodeHelper(&((*ptr)->leftPtr), value);
		else if(value > (*ptr)->data)
			insertNodeHelper(&((*ptr)->rightPtr), value);
		else
			cout << value << " dup" << endl;
	}
}

Why couldn't *ptr be used? I tried and it doesn't insert any nodes.

template<class NODETYPE>
void Tree<NODETYPE>::insertNode(const NODETYPE &value)
{	insertNodeHelper2(rootPtr, value);	}

template<class NODETYPE>
void Tree<NODETYPE>::insertNodeHelper2(TreeNode<NODETYPE> *ptr, const NODETYPE &value)
{
	if(ptr == 0)
		ptr = new TreeNode<NODETYPE>(value);
	else
	{
		if(value < ptr->data)
			insertNodeHelper2(ptr->leftPtr, value);
		else if(value > ptr->data)
			insertNodeHelper2(ptr->rightPtr, value);
		else
			cout << value << " dup" << endl;
	}
}

All my gratefulness.

[ArkM]

If the tree is empty the insertNodeHelper must change its parameter value - the root pointer (see the 1st if alternative). You need pass a pointer to the root pointer (or reference but it's another song), not only its value. The root pointer type is TreeNode<NODETYPE>*. So parameter type must be (TreeNode<NODETYPE> *)*. Now you can change it with *ptr.

In actual fact this mechanism works not only in empty tree case but for every new node (because of it's recursive algorithm).

The 2nd (wrong) variant sets new node pointer to ptr parameter, but it's by value copy of the pointer to the root node, not the root node pointer variable per se. So your tree never grows.