Skip to content

Instantly share code, notes, and snippets.

@mgechev
Last active October 3, 2022 03:54
Show Gist options
  • Save mgechev/5911348 to your computer and use it in GitHub Desktop.
Save mgechev/5911348 to your computer and use it in GitHub Desktop.
Simple implementation of binary search tree in C++.
#include <iostream>
#include <math.h>
using namespace std;
template <class T>
struct Node {
T value;
Node *left;
Node *right;
Node(T val) {
this->value = val;
}
Node(T val, Node<T> left, Node<T> right) {
this->value = val;
this->left = left;
this->right = right;
}
};
template <class T>
class BST {
private:
Node<T> *root;
void addHelper(Node<T> *root, T val) {
if (root->value > val) {
if (!root->left) {
root->left = new Node<T>(val);
} else {
addHelper(root->left, val);
}
} else {
if (!root->right) {
root->right = new Node<T>(val);
} else {
addHelper(root->right, val);
}
}
}
void printHelper(Node<T> *root) {
if (!root) return;
printHelper(root->left);
cout<<root->value<<' ';
printHelper(root->right);
}
int nodesCountHelper(Node<T> *root) {
if (!root) return 0;
else return 1 + nodesCountHelper(root->left) + nodesCountHelper(root->right);
}
int heightHelper(Node<T> *root) {
if (!root) return 0;
else return 1 + max(heightHelper(root->left), heightHelper(root->right));
}
void printMaxPathHelper(Node<T> *root) {
if (!root) return;
cout<<root->value<<' ';
if (heightHelper(root->left) > heightHelper(root->right)) {
printMaxPathHelper(root->left);
} else {
printMaxPathHelper(root->right);
}
}
bool deleteValueHelper(Node<T>* parent, Node<T>* current, T value) {
if (!current) return false;
if (current->value == value) {
if (current->left == NULL || current->right == NULL) {
Node<T>* temp = current->left;
if (current->right) temp = current->right;
if (parent) {
if (parent->left == current) {
parent->left = temp;
} else {
parent->right = temp;
}
} else {
this->root = temp;
}
} else {
Node<T>* validSubs = current->right;
while (validSubs->left) {
validSubs = validSubs->left;
}
T temp = current->value;
current->value = validSubs->value;
validSubs->value = temp;
return deleteValueHelper(current, current->right, temp);
}
delete current;
return true;
}
return deleteValueHelper(current, current->left, value) ||
deleteValueHelper(current, current->right, value);
}
public:
void add(T val) {
if (root) {
this->addHelper(root, val);
} else {
root = new Node<T>(val);
}
}
void print() {
printHelper(this->root);
}
int nodesCount() {
return nodesCountHelper(root);
}
int height() {
return heightHelper(this->root);
}
void printMaxPath() {
printMaxPathHelper(this->root);
}
bool deleteValue(T value) {
return this->deleteValueHelper(NULL, this->root, value);
}
};
int main() {
BST<int> *bst = new BST<int>();
bst->add(11);
bst->add(1);
bst->add(6);
bst->add(-1);
bst->add(-10);
bst->add(100);
bst->print();
cout<<endl;
cout<<"Nodes count: "<<bst->nodesCount();
cout<<endl;
cout<<"Height: "<<bst->height();
cout<<endl;
cout<<"Max path: ";
bst->printMaxPath();
cout<<endl;
bst->deleteValue(11);
cout<<"11 removed: ";
bst->print();
cout<<endl;
cout<<"1 removed: ";
bst->deleteValue(1);
bst->print();
cout<<endl;
cout<<"-1 removed: ";
bst->deleteValue(-1);
bst->print();
cout<<endl;
cout<<"6 removed: ";
bst->deleteValue(6);
bst->print();
cout<<endl;
cout<<"-10 removed: ";
bst->deleteValue(-10);
bst->print();
cout<<endl;
cout<<"100 removed: ";
bst->deleteValue(100);
bst->print();
cout<<endl;
return 0;
}
@supratikn
Copy link

memory leaks

@MarkKoz
Copy link

MarkKoz commented Dec 7, 2017

root does not have to be initialised in C++ 11. Because no user-defined constructor is given for BST, the compiler implicitly defines a default constructor. During value-initialisation, fields will be zero-initialised because of the presence of this implicitly defined default constructor. Because pointers are a scalar type, they will be initialised to 0 i.e. NULL

@hanseul1795
Copy link

@supratikn, of course, destructor is not implemented.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment