## A quick and dirty BST implementation

Another quick and dirty algorithm implementation in C++. This time a Binary search tree (no balancing):

```#include <iostream>
#include <vector>

using namespace std;

class Node {

public:

int value;

Node *less;
Node *more;
};

class BinarySearchTree {

public:

BinarySearchTree() : root(NULL) {}

void find_node(int value,Node **findnode,Node **parent) {

*findnode = NULL;
*parent   = NULL;

if(root == NULL) {
return;
}

Node *current = root;
for(;;) {
if(current->value == value) {*findnode = current; return;}

if(value < current->value) {
if(current->less != NULL) {*parent = current; current = current->less;}
else {
return;
}
} else {
if(current->more != NULL) {*parent = current; current = current->more;}
else {
return;
}
}
}
}

Node *getr(Node *c,Node **parent) {
*parent = c;
for(;c->more != NULL;) {
*parent = c;
c = c->more;
}
return c;
}

void remove(int value) {

Node *delnode;
Node *parent;

find_node(value,&delnode,&parent);

if(delnode == NULL) return;

// leaf
if((delnode->less == NULL) && (delnode->more == NULL)) {
if(parent->less == delnode) {parent->less = NULL;}
if(parent->more == delnode) {parent->more = NULL;}
delete delnode;
return;
}

// only one child
if((delnode->less == NULL) || (delnode->more == NULL)) {
if(delnode->less != NULL) {
if(parent->less == delnode) {parent->less = delnode->less;}
if(parent->more == delnode) {parent->more = delnode->less;}
delete delnode;
return;
}

if(delnode->more != NULL) {
if(parent->less == delnode) {parent->less = delnode->more;}
if(parent->more == delnode) {parent->more = delnode->more;}
delete delnode;
return;
}
}

// two children
Node *i = getr(delnode->less,&parent);

delnode->value = i->value;
if(parent == i)       { delnode->less = NULL;}
if(parent->less == i) { parent->less = NULL; }
else { parent->more = NULL; }
delete i;
}

void insert(int value) {

if(root == NULL) {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
root = n;

return;
}

Node *current = root;
for(;;) {
if(value < current->value) {
if(current->less != NULL) current = current->less;
else {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
current->less = n;
break;
}
} else {
if(current->more != NULL) current = current->more;
else {
Node *n = new Node();
n->value = value;
n->less = NULL;
n->more = NULL;
current->more = n;
break;
}
}
}
}

bool exists(int value) {
if(root == NULL) {
return false;
}

Node *current = root;
for(;;) {
if(current->value == value) return true;

if(value < current->value) {
if(current->less != NULL) current = current->less;
else {
return false;
}
} else {
if(current->more != NULL) current = current->more;
else {
return false;
}
}
}
}

Node *root;
};

int main() {

BinarySearchTree s;

vector<int> testdata;

for(size_t n=0;n<10;n++) { testdata.push_back(rand()%20); }

for(size_t n=0;n<10;n++) { s.insert(testdata[n]); }

cout << "testdata: " << endl;
for(size_t n=0;n<10;n++) { cout << testdata[n] << endl; }

cout << "existance check: " << endl;
for(size_t n=0;n<10;n++) { if(s.exists(testdata[n])) cout << "existance: " << testdata[n] << " true" << endl; else cout << "existance: " << testdata[n] << " false" << endl;}
for(size_t n=0;n<10;n++) { if(s.exists(testdata[n]+20)) cout << "existance: " << testdata[n]+20 << " true" << endl; else cout << "existance: " << testdata[n]+20 << " false" << endl;}

cout << "remove: " << testdata[5] << endl;
s.remove(testdata[5]);
if(s.exists(testdata[5])) cout << testdata[5] << " still exists" << endl; else cout << testdata[5] << " no longer exists" << endl;

cout << "remove: " << testdata[3] << endl;
s.remove(testdata[3]);
if(s.exists(testdata[3])) cout << testdata[3] << " still exists" << endl; else cout << testdata[3] << " no longer exists" << endl;

cout << "remove: " << testdata[0] << endl;
s.remove(testdata[0]);
if(s.exists(testdata[0])) cout << testdata[0] << " still exists" << endl; else cout << testdata[0] << " no longer exists" << endl;
}
```