### Binary Search Tree Remove

I don't know why, but my remove function doesn't seem to operate properly. The rest of my code is fine, so I am trying to pinpoint the exact location of my error. The else if statement remove(root->left, data) should've been called twice, but it only called once. Is anyone able to assist me

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061`` ``````BST* smallestNode(BST* root) // precondition: T is not null // postcondition: return the node in the subtree rooted at T that // has the smallest value { if (root->left == NULL) return root; else return smallestNode(root->left); } BST* remove(BST* root, int data){ if (root == NULL) return 0; if (data == root->data){ if(root->left == NULL && root->right == NULL){ delete(root); } else if (root->left == NULL){ cout <<"runs here????"<right; delete(root->right); } else if (root->right == NULL){ cout<<"runs here?"<left; delete(root->left); } else if (root->left != NULL && root->right != NULL){ BST* temp = smallestNode(root->right); root = temp; delete(temp); } } if (data > root->data){ remove(root->right, data); } else if (data < root->data){ cout <<"here"<left, data); } return 0; } int main(){ BST* tree = init(5); int a[8] = {1, 3, 5, 6, 3, 9, 10, 46}; for (unsigned int i = 0; i < sizeof(a)/sizeof(int); i++) insert(tree, a[i]); if (find(tree, 5)) cout << "true" << endl; else cout <<"false"<
If line 18 executes, what happens on line 37? Your root no longer points to a valid object, so root->data is undefined behavior.

If line 23 executes and root->right has children, what happens to those children? Do previous pointers to the deleted node still point to the invalid node?

If line 28 executes and root->left has children, what happens to those children? Do previous pointers to the deleted node still point to the invalid node?
Last edited on
Ok I think I see what you're saying. On line 35, I should return root, so that if I just delete the root, I would return Null as the value that is being removed.
Topic archived. No new replies allowed.