'Finding the parent of a node in a binary tree using a recursive function
I know this one has been asked many times before but I could not find an answer that solves the problem in my implementation. The struct I'm using:
typedef struct STnode* link;
typedef struct STnode {Item item; link l, r; int N;}STnode;
link NULLnode;
Insertion functions:
link NEW(Item item, link l, link r, int N)
{
link x = malloc(sizeof *x);
x->item = item;
x->l = l;
x->r = r;
x->N = N;
return x;
}
void InsertLeft (link node, Item item)
{
node->l = NEW (item, NULLnode, NULLnode, 1);
}
void InsertRight(link node, Item item)
{
node->r = NEW(item, NULLnode, NULLnode, 1);
}
void BTinsertR (link node, Item item)
{
InsertRight(node, item);
}
void BTinsertL (link node, Item item)
{
InsertLeft(node, item);
}
Finally the problem function that I have been banging my head against for hours. It's supposed to return the item of the parent of the given node.
Item Parent(link root, link node)
{
Item temp;
if (root==node)
{
printf("The given node is root of a tree and thus has no parent\n");
return NULLitem;
}
else if(root == NULLnode)
{
return temp;
}
else if(root->l==node || root->r==node)
{
temp = root->item;
printf("Item of parent's node: %d\n", temp);
return temp;
}
else
{
Parent(root->l, node);
Parent(root->r, node);
}
return temp;
}
Instead it prints the right item but returns the item of the last node I insert. The only time I alter the value of temp is when I find the node, so how is it possible that it changes at the last call?
EDIT: Forgot to add, my items are simple integers and the main function is
int main(int argc, char *argv[])
{
Item item = ITEMscan();
NULLmaker();
link root1 = MakeTree(item);
item = ITEMscan();
link root2 = MakeTree(item);
item = ITEMscan();
BTinsertL(root1, item);
item = ITEMscan();
BTinsertR(root1, item);
item = ITEMscan();
BTinsertL(root1->l, item);
item = ITEMscan();
BTinsertR(root1->l, item);
item = ITEMscan();
BTinsertL((root1->l)->l, item);
Parent(root1, (root1->l)->l);
return 0;
}
MakeTree simply initializes the tree
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
