From 74148d4942ada0b0e1a7a00d10e4c68ff1c6bcfd Mon Sep 17 00:00:00 2001
From: Santo Cariotti <sancn@live.com>
Date: Wed, 1 Nov 2017 16:38:47 +0100
Subject: added binary search tree

---
 cpp/bst.cc | 105 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 105 insertions(+)
 create mode 100644 cpp/bst.cc

diff --git a/cpp/bst.cc b/cpp/bst.cc
new file mode 100644
index 0000000..bc9efaf
--- /dev/null
+++ b/cpp/bst.cc
@@ -0,0 +1,105 @@
+#include <iostream>
+
+using namespace std;
+
+struct Node {
+	int data;
+	Node *right, *left;
+	Node(int _data, Node *r = nullptr, Node* l = nullptr) : data(_data), right(r), left(l) {}
+};
+
+class BST {
+private:
+	Node *root;
+	
+	void insert(Node* root, int data) {
+		if(root->data > data) {
+			if(!root->left) {
+				root->left = new Node(data);
+			} else {
+				insert(root->left, data);
+			}
+		} else {
+			if(!root->right) {
+				root->right = new Node(data);
+			} else {
+				insert(root->right, data);
+			}
+		}
+	}
+	
+	Node* min(Node *root) {
+		while(root->left != nullptr) root = root->left;
+		return root;
+	}
+
+	Node* remove(Node* root, int data) {
+		if(root->data > data) root->left = remove(root->left, data);
+		else if(root->data < data) root->right = remove(root->right, data);
+		else {
+			if(root->right == nullptr && root->left == nullptr) {
+				delete root;
+				root = nullptr;
+			} else if(root->right == nullptr) {
+				Node* tmp = root->left;
+				delete root;
+				return tmp;
+			} else if(root->left == nullptr) {
+				Node* tmp = root->right;
+				delete root;
+				return tmp;
+			}
+			
+			Node* tmp = min(root->right);
+			root->data = tmp->data;
+			root->right = remove(root->right, tmp->data);
+		}
+		
+		return root;
+	}
+	void printBST(Node* root) {
+		if(!root) return;
+
+		printBST(root->left);
+		cout << root->data << ' ';
+		printBST(root->right);
+	}
+
+public:
+	void add(int data) {
+		if(root) {
+			this->insert(root, data);
+		} else {
+			root = new Node(data); 
+		}
+		
+	}
+	
+	void rem(int data) {
+		if(root) {
+			this->remove(root, data);
+		} else return;
+	}
+
+	void print() {
+		printBST(this->root);
+	}
+};
+
+int main() {
+	BST* bst = new BST();
+	
+	for(int i = 0; i < 9; i++) {
+		int zz;
+		std::cin >> zz;
+		bst->add(zz);
+	}
+	int zz;
+	std::cin >> zz;
+	bst->rem(zz);
+	bst->print();
+
+	delete bst;
+
+	return 0;
+}
-- 
cgit v1.2.3-18-g5258