Getting the parent of a node in a binary tree

budala · 09-18-2009, 10:45 AM

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.

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);
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

tabstop · 09-18-2009, 11:08 AM

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.

budala · 09-18-2009, 11:19 AM

1. obviously I don't know

2. would you mind helping me a bit more?

tabstop · 09-18-2009, 11:25 AM

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.

itCbitC · 09-18-2009, 12:36 PM

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.

09-18-2009, 10:45 AM	#1
budala Registered User Join Date: Apr 2009 Posts: 48	Inserting a node in a binary tree with a field for the parrent 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. 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); 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 Last edited by budala; 09-18-2009 at 10:51 AM.
budala is offline

09-18-2009, 11:08 AM	#2
tabstop and the Hat of Guessing Join Date: Nov 2007 Posts: 8,740	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.
tabstop is offline

09-18-2009, 11:19 AM	#3
budala Registered User Join Date: Apr 2009 Posts: 48	1. obviously I don't know 2. would you mind helping me a bit more?
budala is offline

09-18-2009, 11:25 AM	#4
tabstop and the Hat of Guessing Join Date: Nov 2007 Posts: 8,740	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.
tabstop is offline

09-18-2009, 12:36 PM	#5
itCbitC Registered User Join Date: Oct 2008 Location: TX Posts: 1,262	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.
itCbitC is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Balancing A Binary Tree	mike_g	C Programming	5	08-12-2008 04:01 PM
arrays vs lists? And containers in general!	clegs	C++ Programming	22	12-03-2007 02:02 PM
Binary Search Trees Part III	Prelude	A Brief History of Cprogramming.com	16	10-02-2004 03:00 PM
Big help in Astar search code...	alvifarooq	C++ Programming	6	09-24-2004 11:38 AM
Binary Tree Search	C++Newbie	C++ Programming	5	03-22-2002 12:38 PM