Member Avatar for 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.

  • 2 Contributors
  • 1 Reply
  • 124 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by ArkM

Dani AI

Generated

— is right: the helper must be able to change the actual pointer stored in the tree (the root or a left/right child). Passing a plain TreeNode* gives the function a copy; assigning to that copy does not change the caller's pointer. Below are clearer, safer alternatives and a few debugging tips.

A more readable alternative to TreeNode** is a reference-to-pointer (TreeNode* &). That lets the helper assign the caller's pointer directly:

template<class T>
void insertNodeHelper(TreeNode<T>*& ptr, const T& value) {
    if (ptr == nullptr)
        ptr = new TreeNode<T>(value);
    else if (value < ptr->data)
        insertNodeHelper(ptr->leftPtr, value);
    else if (value > ptr->data)
        insertNodeHelper(ptr->rightPtr, value);
}

Another common pattern is to return the (possibly new) subtree root and have the caller assign it. That avoids pointer-to-pointer/reference parameters:

template<class T>
TreeNode<T>* insertNodeHelper(TreeNode<T>* ptr, const T& value) {
    if (!ptr) return new TreeNode<T>(value);
    if (value < ptr->data) ptr->leftPtr = insertNodeHelper(ptr->leftPtr, value);
    else if (value > ptr->data) ptr->rightPtr = insertNodeHelper(ptr->rightPtr, value);
    return ptr;
}

Troubleshooting tips: when insertion appears to "not work", check whether the root (or the child pointer you expect to change) actually gets assigned. Print addresses or step in with a debugger to see whether new returns a non-null pointer and whether that address is copied back to the tree's field. Also ensure you manage ownership: add a proper destructor or prefer std::unique_ptr for child links to avoid leaks and make ownership clear. For reference semantics and smart-pointer patterns, see C++ reference docs and unique_ptr documentation on cppreference: unique_ptr.

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.