When to use pointer to pointer in C++?

[funprogrammer]

I was looking through this code for ternary search tree. I was not understanding when we use double pointer in c++? I tried changing the Node** to Node* it did not work. Any explanation on when and where pointer to pointer is used? Why is it used here?

#include <iostream>
#include <cstdlib>
#define MAX 50
using namespace std;

/*
* Node Declaration
*/
struct Node
{
	char data;
	unsigned isEndOfString : 1;
	Node *left, *eq, *right;
};
/*
* create a new ternary search tree node
*/
Node* newNode(char data)
{
	Node* temp = new Node;
	temp->data = data;
	temp->isEndOfString = 0;
	temp->left = temp->eq = temp->right = NULL;
	return temp;
}
/*
* insert a new word in a Ternary Search Tree
*/
void insert(Node** root, char *word)
{
	if (!(*root))
		*root = newNode(*word);
	if ((*word) < (*root)->data)
		insert(&((*root)->left), word);
	else if ((*word) > (*root)->data)
		insert(&((*root)->right), word);
	else
	{
		if (*(word + 1))
			insert(&((*root)->eq), word + 1);
		else
			(*root)->isEndOfString = 1;
	}
}

/*
* traverse Utility function
*/
void traverseTSTUtil(Node* root, char* buffer, int depth)
{
	if (root)
	{
		traverseTSTUtil(root->left, buffer, depth);
		buffer[depth] = root->data;
		if (root->isEndOfString)
		{
			buffer[depth + 1] = '\0';
			cout << buffer << endl;
		}
		traverseTSTUtil(root->eq, buffer, depth + 1);
		traverseTSTUtil(root->right, buffer, depth);
	}
}
/*
* traverse Ternary Search Tree
*/
void traverseTST(Node* root)
{
	char buffer[MAX];
	traverseTSTUtil(root, buffer, 0);
}
/*
* search a given word in Ternary Search Tree
*/
int searchTST(Node *root, char *word)
{
	if (!root)
		return 0;
	if (*word < (root)->data)
		return searchTST(root->left, word);
	else if (*word >(root)->data)
		return searchTST(root->right, word);
	else
	{
		if (*(word + 1) == '\0')
			return root->isEndOfString;
		return searchTST(root->eq, word + 1);
	}
}

/*
* Main
*/
int main()
{
	Node *root = NULL;
	char s[100];
	insert(&root, "cat");
	insert(&root, "cats");
	insert(&root, "up");
	insert(&root, "bug");
	cout << "Following is traversal of ternary search tree\n";
	traverseTST(root);
	cout << "Enter string to search: ";
	cin >> s;
	if (searchTST(root, s))
		cout << s << " found in Ternary Search Tree" << endl;
	else
		cout << s << " not found in Ternary Search Tree" << endl;
	getchar();
	getchar();
	return 0;
}

[htirwin]

Examine this without using a pointer to pointer.

void insert(Node* root, char *word)
{
	if (!(root))
		root = new Node(*word);
	if ((*word) < (root)->data)
		insert(&((root)->left), word);
	else if ((*word) > (root)->data)
		insert(&((root)->right), word);
	else
	{
		if (*(word + 1))
			insert(&((root)->eq), word + 1);
		else
			(root)->isEndOfString = 1;
	}
}

The parameter node *root, becomes a local variable in the function. You pass in a value to it as an argument, and that value is some integer. You do root = new node(*word);, and now root holds the integer value of the address of the newly allocated node. Then in the end of the function, the local variable root goes out of scope and vanishes into the abyss.

Meanwhile, the variable root, local to main, still has the same integer value it had all along, NULL. In the function you have only modified a copy of it.

But if you pass a pointer to the pointer then you can actually modify it in the function because you have the address to where the original pointer is in memory, you can deference it ( go there ) and change it's actual value.

The lesson is that a pointer is really not much different than an unsigned long long. They are just unsigned integers that happen to be used to store memory addresses. The only thing special about them is that there is syntax for dereferencing, pointer arithmetic etc.

You can use references instead, that's the C++ solution to this problem.

[funprogrammer]

@htirwin: Thanks a lot for helping me out. That was a neat explanation. Can you please tell me how would this function change if I used reference instead of pointer to pointer. Can the input parameter be Node* & root or Node & instead of Node**?

[TwilightSpectre]

You can make the input parameter be Node*& root if you want - that would make it much more readable. That would be the easiest way to change it to.

[funprogrammer]

Thanks @NT3. I used it and changed my implementation to this

void insert(Node*& root, char *word)
{
	if (!root)
		root = newNode(*word);
	if ((*word) < root->data)
		insert((root->left), word);
	else if ((*word) > root->data)
		insert(root->right, word);
	else
	{
		if (*(word + 1))
			insert(root->eq, word + 1);
		else
			root->isEndOfString = 1;
	}
}

I am still feeling difficult to understand the concept and having questions on several things. I am sure I cannot remember or explain this to someone else because I am not sure/aware of how this works. Some of my questions are:
1) What does Node*& correspond to? Is it similar to Node**?
2) What is the use of using Node *& over Node **?
3) Why cannot we use just Node* instead of Node**? htirwin explained that updating local variable will not change the actual value in called function, but we still have one pointer value to update the actual address value right?

Any help on these questions will be really helpful. My complete understanding of pointers is shaky after looking at this problem

[htirwin]

1) What does Node*& correspond to? Is it similar to Node**?
2) What is the use of using Node *& over Node **?

1) It's syntax for passing the pointer by reference. I'm not the one to ask about what a reference technically is under the hood, but you can think of it as though you are passing the pointer itself (changes to it in the function apply to the one in main, they are the same variable), as opposed to without the & where you are just making a copy of it.

2) The pointer to pointer is just passing the address of the variable, root. Every variable has an address in memory.

Why cannot we use just Node* instead of Node**? htirwin explained that updating local variable will not change the actual value in called function, but we still have one pointer value to update the actual address value right?

When this happens, root = new Node(*word);, you assign root the address of the newly allocated Node, and you don't know what address it will be until you get it. It depends on what's available and the algorithm for choosing it.

When the function ends, and the variable root goes out of scope in the function, the address of this allocated Node is lost. The pointer in the main function still points to nothing. Your nodes are out there, but you don't know where.

You have to realize that the variable in main and the one in the function are two different variables. You change one, the other remains the same. You can change the value of the one in the function, but that doesn't do you any good, because you need the one in main to point to the new node. All you have done by passing it as an argument to the function is initialized the variable of the same name in the function to, in this case, NULL.