Thread: Problems implementing a binary tree

I am not understanding why the following code is not working. I am assuming the problem is in the InsertNode function.

Code:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	int value;
	struct Node* left;
	struct Node* right;
} Node;

Node* InitNode(int value);
void InsertNode(Node* node, Node* newnode);
void PrintTree(Node* node);

Node* InitNode(int value)
{
	Node* node = (Node*)malloc(sizeof(Node));
	node->value = value;
	node->left = NULL;
	node->right = NULL;
	return(node);
}

void InsertNode(Node* node, Node* newnode)
{
	if (node == NULL)
	{
		node = newnode;
		return;
	}
	if (newnode->value < node->value)
		InsertNode(node->left, newnode);
	else
		InsertNode(node->right, newnode);
}

void PrintTree(Node* node)
{
	if (node == NULL)
		return;
	PrintTree(node->left);
	printf(" %3d", node->value);
	PrintTree(node->right);
}

int main()
{
	Node* root = InitNode(5);
	Node* left = InitNode(4);
	Node* right = InitNode(6);

	InsertNode(root, left);
	InsertNode(root, right);

	PrintTree(root);

	return(0);
}

When you do node=newnode, you are changing the values passed in to the function -- which means that those changes are not reflected in the main program (hence no node is actually inserted). (We've gone around this bit a couple times in the last few days, so read some recent threads.)

My problem stems from assuming by passing a pointer that I can change the location of where the pointer points to. I carried this over from my experience with integers where I would pass in a pointer to the int, modify that, and when the function was done, the changes persisted.

Apparently, for pointers, I needed to be passing in a pointer to the pointer. It actually does make sense the more I think about it. When passing a value to a function that you want the change to persist you need to pass a pointer to that value (even if it is already a pointer).

Here is my modified insert function which now works:

Code:

void InsertNode(Node** node, Node* newnode)
{
	if ((*node) == NULL)
	{
		*node = newnode;
		return;
	}
	if (newnode->value < (*node)->value)
		InsertNode(&(*node)->left, newnode);
	else
		InsertNode(&(*node)->right, newnode);
}