# Removing a node from a binary tree

Discussion in 'C++' started by Jimmy, Dec 4, 2003.

1. ### JimmyGuest

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, Dec 4, 2003

2. ### JimmyGuest

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.

Jimmy, Dec 4, 2003

3. ### Victor BazarovGuest

> 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, Dec 4, 2003
4. ### Victor BazarovGuest

> 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

Victor Bazarov, Dec 4, 2003
5. ### Ali R.Guest

"Victor Bazarov" <> wrote in message
news:kDJzb.419070\$HS4.3341389@attbi_s01...
> > 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.

Ali R., Dec 4, 2003
6. ### Karl Heinz BucheggerGuest

"Ali R." wrote:
>
> "Victor Bazarov" <> wrote in message
> news:kDJzb.419070\$HS4.3341389@attbi_s01...
> > > 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

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

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Dec 4, 2003
7. ### Ali R.Guest

"Karl Heinz Buchegger" <> wrote in message
news:...
> "Ali R." wrote:
> >
> > "Victor Bazarov" <> wrote in message
> > news:kDJzb.419070\$HS4.3341389@attbi_s01...
> > > "Jimmy" <adfj;fd@dafj;dlf.sds> wrote...
> > > > One thing I forgot to mention is: The solution that I have in my

> > > 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
>
> 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.

Ali R., Dec 4, 2003
8. ### Victor BazarovGuest

"Ali R." <> wrote...
> "Victor Bazarov" <> wrote in message
> news:kDJzb.419070\$HS4.3341389@attbi_s01...
> > > 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

Victor Bazarov, Dec 4, 2003
9. ### Thomas MatthewsGuest

Victor Bazarov wrote:
>
>>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

Thomas Matthews, Dec 4, 2003