Thread: 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