Unsure why my remove function for the binary tree is not working, especially for the case that checks if the node has both a right and a left branch.

C++ binary tree data structure

Binary.h

#pragma once class Node{ public:

int datum; Node *right, *left, *parent; Node(int); };

class Binary{ int size = 0; public:

Node *root; void tree(); void insert(int); Node* search(int); void remove(int); int size_tree(); };

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Binary.cpp

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include "Binary.h" #include using namespace std;

Node::Node(int datum){ this->datum = datum; this->left = 0; this->right = 0; this->parent = 0; }

void Binary::tree(){ this->root = 0; }

void Binary::insert(int datum){ Node *newnode = new Node(datum); if (this->root == NULL){ this->root = newnode; this->root->right = NULL; this->root->left = NULL; this->root->parent = NULL; } else{ Node *current = this->root; while (true){ if (datum > current->datum){ if (current->right) current = current->right; else{ current->right = newnode; newnode->parent = current; break; } } else if(current->datum > datum){ if(current->left) current = current->left; else{ current->left = newnode; newnode->parent = current; break; } } else { throw "Duplicates not allowed."; }

} }

size++; }

Node* Binary::search(int datapoint){ if (!root){ throw "Nothing to search, tree is empty."; } Node *current = this->root; while(true){ if (root->datum == datapoint){ return root; } else if (!current->right && !current->left){ cout << "Datapoint not found, location of last node searched returned." << endl; return current; } else if (datapoint > current->datum){ current = current->right; if (datapoint == current->datum){ return current; } } else{ current = current->left; if(datapoint == current->datum){ return current; } } } }

void Binary::remove(int datum){ Node *current = root; Node *search = this->search(datum); Node *parent = search->parent; if (!search){ throw "Tree is empty or given search datum does not exist."; } if (!search->left && !search->right){ if (!parent){ // if the parent is NULL then only the root exists. this->root = NULL; // Make the tree empty; } else if(parent->datum > datum){ parent->left = NULL; } else{ parent->right = NULL; } } else if (search->right && !search->left){ if (!parent){ // If we find the root and it only has a right branch this->root = search->right; } else{ parent->right = search->right; } search->right->parent = parent; } else if (!search->right && search->left){ if (!parent){ this->root = search->left; } else { parent->left = search->left; } search->left->parent = parent; } else if (search->right && search->left){ current = search->left; while (current->right){ current = current->right; } search->datum = current->datum; current->parent->right = current->left; search = current; if (current->left){ current->parent->left = current->left; } } delete search; size--; }

int Binary::size_tree(){ return this->size; }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////

main.cpp

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include #include "Binary.h" using namespace std;

int main() { Binary tree; tree.tree();

try{ tree.insert(10); tree.insert(19); tree.insert(20); tree.insert(18); tree.insert(5); tree.insert(4); tree.insert(7); tree.insert(8); tree.insert(11); tree.insert(13); tree.insert(12);

cout << "Datum location is: " << tree.search(10) << endl; //for (int i = 0; i < 9 ; i--) //tree.insert(i); cout << "Size is: " << tree.size_tree() << endl; tree.remove(10); tree.remove(5); cout << "Datum location is: " << tree.search(5) << endl;

cout << "Datum location is: " << tree.search(7) << endl; cout << "Datum location is: " << tree.search(4) << endl; cout << "Root is: " << tree.root << endl;; } //std::cout << "Requested data " << tree.search(15) << " was found. "; //tree.search(5); //tree.insert(5); //tree.search(8); catch (const char *msg){ cout << msg << endl; } return 0; }