Delete node from Binary Search Tree- Wrong Answer
1
my deletion code for the binary search tree is giving me a Segmentation fault, and I was wondering what the problem was.
The pre-order: 64 8 4 32 16 128 512 256
and the steps run are
removing 4
removing 64
removing 128
and it should result in pre-order: 256 8 32 16 512
but I am getting pre-order: 256 8 0 32 16 512 9502512
my code is below
bool IntBST::remove(int value){
Node* n = getNodeFor(value, root);
if(n == NULL){
return false;
}
else{
if((n->right == NULL) && (n->left == NULL)){
if(n->parent->left == n){
n->parent->left == NULL;
}
else{
n->parent->right == NULL;
}
delete n;
return true;
}
if(n->left && (n->right == NULL)){
n->parent->left = n->left;
n->left->parent = n->parent;
n->left =NULL;
delete n;
return true;
}
if(n->right && (n->left == NULL)){
n->parent->right = n->right;
n->right->parent = n->parent;
n->right =NULL;
delete n;
return true;
}
else{
Node* n2 = getSuccessorNode(n->info);
int temp = n2->info;
remove(n2->info);
n->info = temp;
delete n2;
return true;
}
}
c++ binary-search-tree
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
add a comment |
1
my deletion code for the binary search tree is giving me a Segmentation fault, and I was wondering what the problem was.
The pre-order: 64 8 4 32 16 128 512 256
and the steps run are
removing 4
removing 64
removing 128
and it should result in pre-order: 256 8 32 16 512
but I am getting pre-order: 256 8 0 32 16 512 9502512
my code is below
bool IntBST::remove(int value){
Node* n = getNodeFor(value, root);
if(n == NULL){
return false;
}
else{
if((n->right == NULL) && (n->left == NULL)){
if(n->parent->left == n){
n->parent->left == NULL;
}
else{
n->parent->right == NULL;
}
delete n;
return true;
}
if(n->left && (n->right == NULL)){
n->parent->left = n->left;
n->left->parent = n->parent;
n->left =NULL;
delete n;
return true;
}
if(n->right && (n->left == NULL)){
n->parent->right = n->right;
n->right->parent = n->parent;
n->right =NULL;
delete n;
return true;
}
else{
Node* n2 = getSuccessorNode(n->info);
int temp = n2->info;
remove(n2->info);
n->info = temp;
delete n2;
return true;
}
}
c++ binary-search-tree
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
1
Why do you delete a different node in the last case and not the one you searched for? Also, what is parent pointing to for the top node?
– stark
Nov 15 '18 at 23:10
parent is pointing to NULL in the top node, and I was deleting the successor node because I'm supposed to switch the values r
– Vikram Pasupathy
Nov 15 '18 at 23:17
1
Debugger. Use a debugger. A debugger allows you to single step through your code watching values of variables. Often, using a debugger is faster than correctly posting to StackOverflow and waiting for somebody to inspect or debug your program for you. Also, draw the node and links as you debug the tree operations.
– Thomas Matthews
Nov 16 '18 at 0:09
1
Welcome to Stack Overflow. Take a look at our help section, with special attention to the page on minimal complete examples. You haven't given us enough to reproduce the error, and the failure case seems too complicated. Do you still get the error if you omit the 12? What if you don't remove the 4? Simplify.
– Beta
Nov 16 '18 at 0:35
add a comment |
1
1
1
my deletion code for the binary search tree is giving me a Segmentation fault, and I was wondering what the problem was.
The pre-order: 64 8 4 32 16 128 512 256
and the steps run are
removing 4
removing 64
removing 128
and it should result in pre-order: 256 8 32 16 512
but I am getting pre-order: 256 8 0 32 16 512 9502512
my code is below
bool IntBST::remove(int value){
Node* n = getNodeFor(value, root);
if(n == NULL){
return false;
}
else{
if((n->right == NULL) && (n->left == NULL)){
if(n->parent->left == n){
n->parent->left == NULL;
}
else{
n->parent->right == NULL;
}
delete n;
return true;
}
if(n->left && (n->right == NULL)){
n->parent->left = n->left;
n->left->parent = n->parent;
n->left =NULL;
delete n;
return true;
}
if(n->right && (n->left == NULL)){
n->parent->right = n->right;
n->right->parent = n->parent;
n->right =NULL;
delete n;
return true;
}
else{
Node* n2 = getSuccessorNode(n->info);
int temp = n2->info;
remove(n2->info);
n->info = temp;
delete n2;
return true;
}
}
c++ binary-search-tree
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
my deletion code for the binary search tree is giving me a Segmentation fault, and I was wondering what the problem was.
The pre-order: 64 8 4 32 16 128 512 256
and the steps run are
removing 4
removing 64
removing 128
and it should result in pre-order: 256 8 32 16 512
but I am getting pre-order: 256 8 0 32 16 512 9502512
my code is below
bool IntBST::remove(int value){
Node* n = getNodeFor(value, root);
if(n == NULL){
return false;
}
else{
if((n->right == NULL) && (n->left == NULL)){
if(n->parent->left == n){
n->parent->left == NULL;
}
else{
n->parent->right == NULL;
}
delete n;
return true;
}
if(n->left && (n->right == NULL)){
n->parent->left = n->left;
n->left->parent = n->parent;
n->left =NULL;
delete n;
return true;
}
if(n->right && (n->left == NULL)){
n->parent->right = n->right;
n->right->parent = n->parent;
n->right =NULL;
delete n;
return true;
}
else{
Node* n2 = getSuccessorNode(n->info);
int temp = n2->info;
remove(n2->info);
n->info = temp;
delete n2;
return true;
}
}
c++ binary-search-tree
c++ binary-search-tree
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
asked Nov 15 '18 at 23:01
Vikram PasupathyVikram Pasupathy
93
93
1
Why do you delete a different node in the last case and not the one you searched for? Also, what is parent pointing to for the top node?
– stark
Nov 15 '18 at 23:10
parent is pointing to NULL in the top node, and I was deleting the successor node because I'm supposed to switch the values r
– Vikram Pasupathy
Nov 15 '18 at 23:17
1
Debugger. Use a debugger. A debugger allows you to single step through your code watching values of variables. Often, using a debugger is faster than correctly posting to StackOverflow and waiting for somebody to inspect or debug your program for you. Also, draw the node and links as you debug the tree operations.
– Thomas Matthews
Nov 16 '18 at 0:09
1
Welcome to Stack Overflow. Take a look at our help section, with special attention to the page on minimal complete examples. You haven't given us enough to reproduce the error, and the failure case seems too complicated. Do you still get the error if you omit the 12? What if you don't remove the 4? Simplify.
– Beta
Nov 16 '18 at 0:35
add a comment |
1
Why do you delete a different node in the last case and not the one you searched for? Also, what is parent pointing to for the top node?
– stark
Nov 15 '18 at 23:10
parent is pointing to NULL in the top node, and I was deleting the successor node because I'm supposed to switch the values r
– Vikram Pasupathy
Nov 15 '18 at 23:17
1
Debugger. Use a debugger. A debugger allows you to single step through your code watching values of variables. Often, using a debugger is faster than correctly posting to StackOverflow and waiting for somebody to inspect or debug your program for you. Also, draw the node and links as you debug the tree operations.
– Thomas Matthews
Nov 16 '18 at 0:09
1
Welcome to Stack Overflow. Take a look at our help section, with special attention to the page on minimal complete examples. You haven't given us enough to reproduce the error, and the failure case seems too complicated. Do you still get the error if you omit the 12? What if you don't remove the 4? Simplify.
– Beta
Nov 16 '18 at 0:35
1
1
Why do you delete a different node in the last case and not the one you searched for? Also, what is parent pointing to for the top node?
– stark
Nov 15 '18 at 23:10
Why do you delete a different node in the last case and not the one you searched for? Also, what is parent pointing to for the top node?
– stark
Nov 15 '18 at 23:10
parent is pointing to NULL in the top node, and I was deleting the successor node because I'm supposed to switch the values r
– Vikram Pasupathy
Nov 15 '18 at 23:17
parent is pointing to NULL in the top node, and I was deleting the successor node because I'm supposed to switch the values r
– Vikram Pasupathy
Nov 15 '18 at 23:17
1
1
Debugger. Use a debugger. A debugger allows you to single step through your code watching values of variables. Often, using a debugger is faster than correctly posting to StackOverflow and waiting for somebody to inspect or debug your program for you. Also, draw the node and links as you debug the tree operations.
– Thomas Matthews
Nov 16 '18 at 0:09
Debugger. Use a debugger. A debugger allows you to single step through your code watching values of variables. Often, using a debugger is faster than correctly posting to StackOverflow and waiting for somebody to inspect or debug your program for you. Also, draw the node and links as you debug the tree operations.
– Thomas Matthews
Nov 16 '18 at 0:09
1
1
Welcome to Stack Overflow. Take a look at our help section, with special attention to the page on minimal complete examples. You haven't given us enough to reproduce the error, and the failure case seems too complicated. Do you still get the error if you omit the 12? What if you don't remove the 4? Simplify.
– Beta
Nov 16 '18 at 0:35
Welcome to Stack Overflow. Take a look at our help section, with special attention to the page on minimal complete examples. You haven't given us enough to reproduce the error, and the failure case seems too complicated. Do you still get the error if you omit the 12? What if you don't remove the 4? Simplify.
– Beta
Nov 16 '18 at 0:35
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53329086%2fdelete-node-from-binary-search-tree-wrong-answer%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53329086%2fdelete-node-from-binary-search-tree-wrong-answer%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Why do you delete a different node in the last case and not the one you searched for? Also, what is parent pointing to for the top node?
– stark
Nov 15 '18 at 23:10
parent is pointing to NULL in the top node, and I was deleting the successor node because I'm supposed to switch the values r
– Vikram Pasupathy
Nov 15 '18 at 23:17
1
Debugger. Use a debugger. A debugger allows you to single step through your code watching values of variables. Often, using a debugger is faster than correctly posting to StackOverflow and waiting for somebody to inspect or debug your program for you. Also, draw the node and links as you debug the tree operations.
– Thomas Matthews
Nov 16 '18 at 0:09
1
Welcome to Stack Overflow. Take a look at our help section, with special attention to the page on minimal complete examples. You haven't given us enough to reproduce the error, and the failure case seems too complicated. Do you still get the error if you omit the 12? What if you don't remove the 4? Simplify.
– Beta
Nov 16 '18 at 0:35