Find the parent node of a node in binary search tree
Solution 1
It appears that 45
does not have a left
node, it is NULL
, so checking pRoot->pleft->value == value
is undefined behavior.
30
/ \
15 45
/ \ \
7 17 69
\
80
So you need to do a check, something like:
Node* BST::searchforparentnode(Node* pRoot, int value)
{
if(pRoot->pleft == NULL && pRoot->pright == NULL)
return NULL;
if( (pRoot->pleft != NULL && pRoot->pleft->value == value)
|| (pRoot->pright != NULL && pRoot->pright->value == value))
return pRoot;
if(pRoot->value > value)
return searchforparentnode(pRoot->pleft,value);
if(pRoot->value < value)
return searchforparentnode(pRoot->pright,value);
}
However, another thing to check for is if pRoot
itself is NULL
:
Node* BST::searchforparentnode(Node* pRoot, int value)
{
if (pRoot == NULL)
return NULL;
if(pRoot->pleft == NULL && pRoot->pright == NULL)
return NULL;
if( (pRoot->pleft != NULL && pRoot->pleft->value == value)
|| (pRoot->pright != NULL && pRoot->pright->value == value))
return pRoot;
if(pRoot->value > value)
return searchforparentnode(pRoot->pleft,value);
if(pRoot->value < value)
return searchforparentnode(pRoot->pright,value);
}
Solution 2
Your Problem is:
if(pRoot->pleft->value == value || pRoot->pright->value == value)
because before you checked if left AND right is null. In the section mentioned above, one could be null
You maybe wanna Change your code to something like this:
Node* BST::searchforparentnode(Node* pRoot, int value)
{
if(pRoot->pleft == NULL && pRoot->pright == NULL)
return NULL;
//Added check
if(pRoot->pleft && pRoot->pleft->value == value)
return pRoot;
//Added check
if(pRoot->pright && pRoot->pright->value == value)
return pRoot;
//Check also needed here
if(pRoot->pleft && pRoot->value > value)
return searchforparentnode(pRoot->pleft,value);
//Check also needed here
if(pRoot->pright && pRoot->value < value)
return searchforparentnode(pRoot->pright,value);
}
IMHO: You could also create a pointer to the parent node in each node. This could Speed up certain things a lot!
Admin
Updated on June 05, 2022Comments
-
Admin almost 2 years
So I want to find the parent node of a Node in a binary tree. Suppose that I input 30,15,17,45,69,80,7 in the tree through a text file.
The tree should be
30 15 45 7 17 69 80
And here is my code :
Node* BST::searchforparentnode(Node* pRoot, int value) { if(pRoot->pleft == NULL && pRoot->pright == NULL) return NULL; if(pRoot->pleft->value == value || pRoot->pright->value == value) return pRoot; if(pRoot->value > value) return searchforparentnode(pRoot->pleft,value); if(pRoot->value < value) return searchforparentnode(pRoot->pright,value);
}
In this case i'm not consider if the user input the value of the Root node.
Thing is, when I input 15,17,7, all the value in the left branch of Root node, it came out ok. But when i want to find parent Node of the values from the right branch (69,80) EXCEPT for 45, the program stop running.
Any idea about what caused this error guys? Thanks for reading.
-
Admin almost 9 yearsThank you. I understand now and I will try creating pointers to point back to the parents. That would certainly speeds thing up
-
Admin almost 9 yearsThanks for helping. I see my problem now.