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;
}
@rprtr258
Copy link

rprtr258 commented Apr 9, 2016

Добавьте в конструктор Node обнуление указателей
Node(T val) {
this->value = val;
this->left = this->right = nullptr; //C++11
//или this->left = this->right = NULL; //C++98
}

@lnrsoft
Copy link

lnrsoft commented May 26, 2016

well done mate, nice implementation

@ralphjoseph
Copy link

very neat..I concur with chrisbangun

@RodionOrets
Copy link

binary search tree without balancing......................)

@seymoutr
Copy link

very helpful thank you.

@seymoutr
Copy link

One question: What would be the easiest way to implement a deep copy constructor for the BST?

@ghrua
Copy link

ghrua commented Oct 19, 2016

Does the line 15 should be this?

// add * after Node<T>
Node(T val, Node<T> * left, Node<T> * right)

@JACKIEZHAOKAI
Copy link

good implementation

@dmakweba
Copy link

Hi guys, nice to meet you all especially seen the implementation of this BST in c++.
I am very junior on Algorithm and I would like anyone to assist me with basics to implement this BST and others in C++. The main challenge is that I am not good in C++ as well in such away that I don't know how to separate source file, main file and header file. Please, if anyone can redirect/point me where I can have the skills I will appreciate.
Rgds.

@jhalakpatel
Copy link

@dmakweba you can check out my implementation on BST here

@xiuquanw
Copy link

make sure to initialize pointers in the constructor, otherwise, it will throw segmentation fault.
The line 12 should be this
Node(int val) : value(val) , left(NULL) , right(NULL) {}

@suhussai
Copy link

suhussai commented Oct 28, 2017

To add to @xiuquanw's comment, the root variable in the BST class should be initialized to NULL. So instead of this:

Node<T> *root;

Add this:

Node<T> *root = NULL;

This is to ensure that when setting up the BST, the root is properly created in line 108.

@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