446,190 Members | 833 Online
Need help? Post your question and get tips & solutions from a community of 446,190 IT Pros & Developers. It's quick & easy.

# Removing a node from a binary tree

 P: n/a 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::Delete(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!?!? { } } Jul 22 '05 #1
8 Replies

 P: n/a 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. Jul 22 '05 #2

 P: n/a "Jimmy" wrote... 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::Delete(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 Jul 22 '05 #3

 P: n/a "Jimmy" 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 Jul 22 '05 #4

 P: n/a "Victor Bazarov" wrote in message news:kDJzb.419070\$HS4.3341389@attbi_s01... "Jimmy" 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 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. Jul 22 '05 #5

 P: n/a "Ali R." wrote: "Victor Bazarov" wrote in message news:kDJzb.419070\$HS4.3341389@attbi_s01... "Jimmy" 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 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). -- Karl Heinz Buchegger kb******@gascad.at Jul 22 '05 #6

 P: n/a "Karl Heinz Buchegger" wrote in message news:3F***************@gascad.at... "Ali R." wrote: "Victor Bazarov" wrote in message news:kDJzb.419070\$HS4.3341389@attbi_s01... "Jimmy" 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 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. Jul 22 '05 #7

 P: n/a "Ali R." wrote... "Victor Bazarov" wrote in message news:kDJzb.419070\$HS4.3341389@attbi_s01... "Jimmy" 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 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 Jul 22 '05 #8

 P: n/a Victor Bazarov wrote: "Jimmy" wrote...One thing I forgot to mention is: The solution that I have in my head is toreplace the the node that is begin deleted with the left most node of it'sright 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 Jul 22 '05 #9

### This discussion thread is closed

Replies have been disabled for this discussion.