## Binary Search Trees! Simple Class in C++

Here is a really basic binary tree class, it just includes the basics of creating, inserting, erasing, and returning size. In later posts I will talk about printing and traversals.

This class also uses the Node.h talked about in this earlier post. You’ll notice that I really like to use recursion, I think this is cleaner than looping.

```#include <assert.h>
#include "Node.h"
using namespace std;

class Bst
{
public:

//constructor for when a head Node is provided and when it is not
Bst() {
root = nullptr;
}

Bst(Node *np) {
root = np;
}

//destroy the tree, we need to go through and destroy each node
~Bst() {
destroyTree(root);
}

//get the number of nodes in the tree
int size() {
return size(root);
}

//erase a value in the tree
void erase(int item) {
erase(item, root);
}

//insert a Node in the tree
void insert(int item) {
insert(item, root);
}

private:

Node* root;

//Go through each branch and recursively destroy all Nodes
void destroyTree(Node*& n) {
if (n != nullptr) {
destroyTree(n->left);
destroyTree(n->right);
delete n;
}
}

//For each Node return the number of left and right nodes
//Add it up recursively to get the total size
int size(Node* n) {
if (n != nullptr) {
int left = size(n->left);
int right = size(n->right);
int self = 1;
return left + self + right;
}
return 0;
}

//Find the minimum Node value
Node* findMin(Node* n){
assert(n != nullptr);
if (n->left != nullptr) {
return findMin(n->left);
}
return n;
}

//this one is a beast
//look through all the nodes recursively
//once you find the node value there are numerous cases we need to look for
//If the current node does not have left and right nodes, just delete it
//If it does have a left or right node, set the child to the parent
//If it has both left and right, we need to work some magic. First we find
//the smallest value and set the node we want to delete to that value (removing it)
void erase(int item, Node*& n) {
if (n != nullptr) {
if (item == n->data) {
if (n->right == nullptr && n->left == nullptr) {
delete n;
n = nullptr;
} else if (n->right == nullptr) {
Node* temp = n;
n = n->left;
delete n;
} else if (n->left == nullptr){
Node* temp = n;
n = n->right;
delete n;
} else {
Node *temp = findMin(n->right);
n->data = temp->data;
erase(item, n->right);
}
} else if (item < n->data) {
erase(item, n->left);
} else {
erase(item, n->right);
}
}
}

//look through all the nodes
//insert the node on the correct node, it will be added to the left if the value is less
//added to the right if the value is greater
void insert(int item, Node*& n) {
if (n != nullptr) {
if (item < n->data) {
insert(item, n->left);
} else {
insert(item, n->right);
}
} else {
n = new Node(item);
}
}
};
```

Let me know if you have any improvements or comments!

## Simple List Class in C++

Here is an example of a simple List class I wrote. Follow the comments to understand what is going on. This uses the node structure I wrote about here.

Best of luck!

```#include <cstdlib>
#include "Node.h" //Your Node class, see previous post

using namespace std;

class List
{
public:
List(){
}
~List(){
}
void append(int d){
}
void print(){
}
void insertInOrder(int d){
}
bool findValue (int d){
}
int getSize(){
}

private:
Node *head; //Remember this struct from the previous post

/* Destroy the list
* We recursively call the destroy function to cycle through a list to the end.
* Once the end node is reached, it is deleted. Then as we progress back through
* our recursive call, each associated node is deleted from the end up.
* This is called by our destructor to clean everything up.
*/
void destroyList(Node *n){
if (n->next != nullptr){
destroyList(n->next);
}
delete n;
}

/* Add a Node to the end of a list
* Use recursion to cycle through the list to the end
* Once the end is reached, the next pointer of the last node will by nullptr.
* A new Node will then be inserted replacing that nullptr and chaining to the list
*/
Node* append(Node *n, int d){
if (n == nullptr){
return new Node(d);
}
else {
n->next= append(n->next, d);
}
return n;
}

/* Print the List
* Use recursion to loop through and print each Node in a list
*/
void print(Node *n){
cout << n->data << endl;
if (n->next != nullptr){
print(n->next);
}
}

/* Insert a Node in Numeric order
* Loop throug a list using recursion
* Once the inserting value is less than the current Node
* we know we need to insert the Node in that position
* else we keep cycling through
*/
Node* insertInOrder(Node *n, int d){
if (n == nullptr){
return new Node(d);
}
else if (d > n->data){
n->next= insertInOrder(n->next, d);
}
else {
Node* temp = n; //Temp copy
n = new Node(d); //Set the pointer to a new Node
n->next = temp; //Chain the original onto the new Node's next pointer
}
return n;
}

/* Find a Node
* Loop through the enitre list using recursion
* Return true once the Node value we want is found
*/
bool findValue(Node *n, int d){
if (n->data == d){
return true;
}
else if(n->next != nullptr){
return findValue(n->next, d);
}
return false;
}

/* Get the Size of a List
* Use recursion to cycle through the list
* all the while keeping a counter going of each Node encountered
*/
int getSize(Node *n, int i = 0){
if (n != nullptr){
++i;
return getSize(n->next, i);
}
return i;
}

};```