Removing a node from a binary tree

[Jimmy]

Hi everyone,

I am working with a binary tree, and I am having a bit of trouble
visuallizing what needs to happen when I am trying to
delete a node that has two children. (no child node and one child node were
trivial).

Does anyone know the solution to this problem?

void CTree:elete(CPerson *&pPerson)
{
if (pPerson->pLeft == NULL && pPerson->pRight == NULL)
{
delete pPerson;
pPerson = NULL;
}
else if (pPerson->pLeft == NULL)
{
CPerson *pTemp = pPerson;
pPerson = pPerson->pRight;
delete pTemp;
}
else if (pPerson->pRight == NULL)
{
CPerson *pTemp = pPerson;
pPerson = pPerson->pLeft;
delete pTemp;
}
else //if the right and left are not null!?!?
{
}
}

 

[Jimmy]

One thing I forgot to mention is: The solution that I have in my head is to
replace the the node that is begin deleted with the left most node of it's
right child. But not sure if that will work in all cases.

 

[Victor Bazarov]

I am working with a binary tree, and I am having a bit of trouble
visuallizing what needs to happen when I am trying to
delete a node that has two children. (no child node and one child node were
trivial).

Does anyone know the solution to this problem?

I think you need to find a leaf that is between the left and the right
nodes and move it into the "deleted" node.

void CTree:elete(CPerson *&pPerson)
{
if (pPerson->pLeft == NULL && pPerson->pRight == NULL)
{
delete pPerson;
pPerson = NULL;
}
else if (pPerson->pLeft == NULL)
{
CPerson *pTemp = pPerson;
pPerson = pPerson->pRight;
delete pTemp;
}
else if (pPerson->pRight == NULL)
{
CPerson *pTemp = pPerson;
pPerson = pPerson->pLeft;
delete pTemp;
}
else //if the right and left are not null!?!?
{

// this is a bit more complicated.
// you need to search the left and right for a leaf node
// that is smaller than right and greater than left
// then prune that leaf and stick the value in *this.

}
}

I may be mistaken, of course. That's all off the top of my head.

Victor

 

[Victor Bazarov]

One thing I forgot to mention is: The solution that I have in my head is to
replace the the node that is begin deleted with the left most node of it's
right child. But not sure if that will work in all cases.

It probably will. The leftmost [leaf] node of the right child is
(a) greater than the current node (otherwise it would be in the left
child) and (b) the smallest in the right subtree (otherwise it would
not be the leftmost). So, with the current node gone, it's the
primary candidate for its place

Victor

 

[Ali R.]

One thing I forgot to mention is: The solution that I have in my head is to
replace the the node that is begin deleted with the left most node of it's
right child. But not sure if that will work in all cases.

It probably will. The leftmost [leaf] node of the right child is
(a) greater than the current node (otherwise it would be in the left
child) and (b) the smallest in the right subtree (otherwise it would
not be the leftmost). So, with the current node gone, it's the
primary candidate for its place

Victor

What about a case like this

10
/ \
2 19
/ \ / \
1 4 14 20
\
15
if you try to delete 10, and replace it with the left most node of it's
right node (which is 14). what will happen to 15?

Ali R.

 

[Karl Heinz Buchegger]

One thing I forgot to mention is: The solution that I have in my head is to
replace the the node that is begin deleted with the left most node of it's
right child. But not sure if that will work in all cases.

It probably will. The leftmost [leaf] node of the right child is
(a) greater than the current node (otherwise it would be in the left
child) and (b) the smallest in the right subtree (otherwise it would
not be the leftmost). So, with the current node gone, it's the
primary candidate for its place

Victor

What about a case like this

10
/ \
2 19
/ \ / \
1 4 14 20
\
15
if you try to delete 10, and replace it with the left most node of it's
right node (which is 14). what will happen to 15?

Is this question addressed to the OP (you want to make him think
about some cases), or are you asking for yourself?

If first, I apologize for interfering.
else scroll down a little bit









































15 has to be reconnected to 20 (if the leftmost child of
the right subtree has a right child on its own, then this
child will replace that leftmost child).

 

[Ali R.]

One thing I forgot to mention is: The solution that I have in my head is
to
replace the the node that is begin deleted with the left most node

of
it's

right child. But not sure if that will work in all cases.

It probably will. The leftmost [leaf] node of the right child is
(a) greater than the current node (otherwise it would be in the left
child) and (b) the smallest in the right subtree (otherwise it would
not be the leftmost). So, with the current node gone, it's the
primary candidate for its place

Victor

What about a case like this

10
/ \
2 19
/ \ / \
1 4 14 20
\
15
if you try to delete 10, and replace it with the left most node of it's
right node (which is 14). what will happen to 15?

Is this question addressed to the OP (you want to make him think
about some cases), or are you asking for yourself?

If first, I apologize for interfering.
else scroll down a little bit

No Apology need!

I was the one butting in to begin with.
I was thinking about a solutions but couldn't seem to find a good one. It's
been 15 years since I have looked at a binary tree. The cumulative solution
from this thread seem to involve alot of IF statements. I was just picking
Victor's brain there.

Ali R.

 

[Victor Bazarov]

One thing I forgot to mention is: The solution that I have in my head

is
to

replace the the node that is begin deleted with the left most node of it's
right child. But not sure if that will work in all cases.

It probably will. The leftmost [leaf] node of the right child is
(a) greater than the current node (otherwise it would be in the left
child) and (b) the smallest in the right subtree (otherwise it would
not be the leftmost). So, with the current node gone, it's the
primary candidate for its place

Victor

What about a case like this

10
/ \
2 19
/ \ / \
1 4 14 20
\
15
if you try to delete 10, and replace it with the left most node of it's
right node (which is 14). what will happen to 15?

Deletion of a node is not a one shot operation. Since '15' is hanging
off the '14', and '14' is the one being deleted, then '15' should take
its place, I believe.

Victor

 

[Thomas Matthews]

One thing I forgot to mention is: The solution that I have in my head is
to

replace the the node that is begin deleted with the left most node of it's
right child. But not sure if that will work in all cases.

It probably will. The leftmost [leaf] node of the right child is
(a) greater than the current node (otherwise it would be in the left
child) and (b) the smallest in the right subtree (otherwise it would
not be the leftmost). So, with the current node gone, it's the
primary candidate for its place

Victor

Ahh, the binary tree; balance and symmetry.

One could also seek out the rightmost leaf node of the left subtree
of the victim node. I'm talking about the victim's predecessor when
traversing in LNR order.

I guess whether to replace the victim node with its predecessor or
successor is a design choice.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book