Getting the parent of a node in a binary tree

I need help with defining a node and inserting it in a binary tree.

If I define a node like this

Code:

typedef struct treenode
{
	int id;
	struct node *Left, *Right;
} node;

then I have no problem with insertion.

Code:

node* NewNode(int id)
{
	node *new = malloc(sizeof(node));
	
	new->id = id;
	new->Left = NULL;
	new->Right = NULL;
	
	return (new);
}

void Insert (node **root, int id)
{
	node *temp = *root;
	if (temp == NULL) *root = NewNode(id);
	else
	{
		if (temp->id == id) printf("DUPLICATE!!!");
		else if (temp->id < id) Insert(&temp->Right, id);
		else Insert(&temp->Left, id);
	}
}

But I need a pointer to the parent of each node. so it should be defined like this

Code:

typedef struct treenode
{
	int id;
	struct node *Left, *Right, *Dad;
} node;

and this is where the problems start.

1. I don't know how to initialize the tree because it seems to me that the root should be initialized beforehand and then I would have problems with the line in Insert() if (temp == NULL) *root = NewNode(id);
2. I don't know how to keep track of the recursive calls so I don't know how to link the new node with the parent

please can someone help me

1. Why would that be a problem? Why would you want to initialize the root beforehand?

2. Your tree-walking code needs to take account of the fact that the parent of the node is needed and "remember" it as it goes down. If you are doing this recursively, then you need another variable in your function call.

1. obviously I don't know
2. would you mind helping me a bit more?

2. Without actually typing the entire code, I doubt it. You need to, when you insert a node, set a parent node pointer to the child (this is done for you by the fact that you pass the address of ->Left or ->Right to the function recursively) and you need to set the parent pointer in the child node, which means you need to be holding onto a pointer to the parent as you walk the tree. So you will need, not just a "where are we now" pointer (your root in the current example) but also a "where did we come from" pointer.

So what is so hard about the advice tabstop gave you. Invoke NewNode() with two arguments; the second argument being the parent of the new node.