# Binary search tree implementation in C++

I've written a BST implementation and would like a code review and any suggestions on how to make it better.

#include<iostream.h>
#include<conio.h>
#include<stack>
#include<queue>
#ifndef BINSTREE
#define BINSTREE
using namespace std;
typedef int valuetype;
/*struct Node{
valuetype data;
Node* left;
Node* right;
};
*/

class Node{
public:
valuetype data;
Node* left;
Node* right;
Node();
Node(valuetype);
};
//OK

class BST{
Node* findNodebyvalue(valuetype);
Node* findparentforNode(valuetype);
Node* findrightnode(Node*);
void inorder(Node*);
void postorder(Node*);
void preorder(Node*);
public:
Node* root;
Node* current;
public:
BST();
void insert(valuetype);
void remove(valuetype);
void traverse();
valuetype retrieve();
void custom_print();
};

//constructor1
Node::Node(){
left=right=NULL;
}
//constructor2
Node::Node(valuetype val){
data=val;
left=right=NULL;
}

//constructor
BST::BST(){
root=current=NULL;
}
//insert a node with value val in tree
void BST::insert(valuetype val){
if(root==NULL)
root = new Node(val);
else{
Node* p =findNodebyvalue(val);
if(p==0)
{
//cout<<"fine1";
Node* parent=root;
if (p != root)
parent = findparentforNode(val);
if(val>parent->data) parent->right=new Node(val);
else parent->left=new Node(val);
}
//cout<<"fine2";
}
}
//remove the node if value is val
void BST::remove(valuetype val){
Node* p = findNodebyvalue(val);
if(p!=0){
//if both of child of node are null(leaf node)
if(p->left==NULL&&p->right==NULL){
if(p!=root){
Node* parent= findparentforNode(val);
if(val<parent->data) parent->left=NULL;
else parent->right=NULL;
}
else root=NULL;
delete (p);
}
//if only left child is not null
else if(p->left!=NULL&&p->right==NULL){
if(p!=root){
Node* parent=findparentforNode(val);
if(val<parent->data) parent->left=p->left;
else parent->right=p->left;
}
else root=NULL;
delete (p);
}
//if only right child is not null
else if(p->left==NULL&&p->right!=NULL){
if(p!=root){
Node* parent=findparentforNode(val);
if(val<parent->data) parent->left=p->right;
else parent->right=p->right;
}
else root=NULL;
delete (p);
}
//if both child are not null
else{
Node* righty=findrightnode(p->left);
Node* parent=findparentforNode(righty->data);
p->data=righty->data;
if(parent!=p) parent->right=righty->left;
else p->left=righty->left;
}
}
}
//fins node with a value key
Node* BST::findNodebyvalue(valuetype key){
Node* p =root;
while((p!=NULL)&&(p->data!=key)){
if(key<p->data)p=p->left;
else p=p->right;
}
return p;
}
//find parent of a node with value key
Node* BST::findparentforNode(valuetype key){
Node* p =root;
Node* q=0;
while((p!=NULL)&&(p->data!=key)){
q=p;
if(key<p->data)p=p->left;
else p=p->right;
}
return q;
}
//finds the most right of a node p(means immediate succesor of p in inorder representation)
Node* BST::findrightnode(Node* p){
Node* righty=p;
while(righty->right!=NULL)
righty=righty->right;
return righty;
}
//inorder
void BST::inorder(Node* p){
if(p!=NULL){
inorder(p->left);
cout<<p->data<<" ";
inorder(p->right);
}
}
//postorder
void BST::preorder(Node* p){
if(p!=NULL){
cout<<p->data<<" ";
preorder(p->left);
preorder(p->right);
}
}
//postorder
void BST::postorder(Node* p){
if(p!=NULL){
postorder(p->left);
postorder(p->right);
cout<<p->data<<" ";
}
}

void BST::traverse(){
cout<<"Preorder: ";
preorder(root);
cout<<endl<<"Inorder: ";
inorder(root);
cout<<endl<<"PostOrder: ";
postorder(root);
cout<<endl;
}

//to print tree hightwise i.e. all nodes at h1, then all nodes at h2, then at h3
void BST::custom_print(){
//Node* temp;
if(root==NULL)
return;
queue<Node*> Q;
Q.push(root);
//Q.push(NULL);
while(!Q.empty()){
current=Q.front();
cout<<current<<" ";
Q.pop();
Q.push(current->left);
Q.push(current->right);
}
}

#endif

int main()
{
BST tree;
tree.insert(10);
tree.insert(2);
tree.insert(4);
tree.insert(12);
tree.insert(23);
tree.traverse();
tree.custom_print();
getch();
return 0;
}

• replace void custom_print(){ with void custom_print(); in your class declaration – saeedn Oct 24 '12 at 7:35
• Fixed typo: It now compiles and runs (as expected). – Martin York Oct 24 '12 at 10:15

This is an old deprecated header don't use it:

#include<iostream.h>

// modern C++ standard headers have dropped the '.h' part
// It is also more visually pleasing to add a space after include
#include <iostream>


This is non standard (MS-DOS specific)

#include<conio.h>

// You only use it to get the program to pause before exiting.
// So you can use some more standard compliant code to do the same thing
// See below for details (but just drop the header)


You seem to have header guards in a source file. Only add these to the header file (I assume this is because of pasting into website). Also they should surround everything in the file (include the #include).

#ifndef BINSTREE
#define BINSTREE


Don't do this:

using namespace std;


It brings everything from standard into the global namespace. This is a problem especially if other people include your header file. The reason std is short so it is not a problem prefixing things with std:: .

Delete all commented out code.

/*struct Node{
valuetype data;
Node* left;
Node* right;
};
*/


It has no place in your code. If you want to remember old code then use version control software. There is lots of free stuff around. A very popular one nowadays is git. You can even host you repos for free on github.com.

Not much point in using a class if everything is public. If you are just using it is a property bag (ie no methods and all the code is in BST) then you can use struct as an indication that this type is not that important.

class Node{
public:
valuetype data;
Node* left;
Node* right;
Node();
Node(valuetype);
};


//OK


The Node class should probably be a private internal member of BST. Are root and current really public (i think you just have not tidied up your code). More visual clues about the layout would be nice. I indent members more that public: and private: to make sure the sections stand out. An extra empty line would not hurt either.

class BST{
Node* findNodebyvalue(valuetype);
Node* findparentforNode(valuetype);
Node* findrightnode(Node*);
void inorder(Node*);
void postorder(Node*);
void preorder(Node*);
public:
Node* root;
Node* current;
public:
BST();
void insert(valuetype);
void remove(valuetype);
void traverse();
valuetype retrieve();
void custom_print();
};


Your class contain RAW pointers (ie not smart pointers). These are owned by the class. Thus you should use RAII to manage them. In this example you just leak memory. But if you had add destructors to clean up the memory then you would not have been following the rule of 3 which would have caused problems if you had made any copies.

~BST();                         // Clean up allocated memory.
BST(BST const& rhs);            // Correctly make a deep copy.
BST& operator=(BST const& rhs); // Correctly do an assignment.
// Look up copy and swap idiom.


Use initializer list in the constructor (and comments like that are usless I can see they are constructors). Comments should be used to explain the how (or why) code is doing what it does. The code should itself be self documenting (ie use good variable and method names that explain what is happening).

Node::Node()
: left(NULL)
, right(NULL)
{}

Node::Node(valuetype val)
: left(NULL)
, right(NULL)
, data(val)
{}

BST::BST()
: root(NULL)
, current(NULL)
{}


Not a very useful comment.

//insert a node with value val in tree


I should hope it inserts a value it is after called insert(). More useful would be notes of any pre/post conditions etc.

void BST::insert(valuetype val){
if(root==NULL)
root = new Node(val);
else{                                // K&R Style brace here
Node* p =findNodebyvalue(val);
if(p==0)
{                              // Aligned brace style here.

// Remove commented out code.
// Or use some form of logging infrastructure you
// can turn on at a more abstract level.
//cout<<"fine1";

// More white space in the code to break sections up
// would also be nice.
Node* parent=root;
if (p != root)
parent = findparentforNode(val);

// Not a fan of this style of if it makes the code hard to read
// Always consistently using braces can keep you out of trouble.
if(val>parent->data) parent->right=new Node(val);
else parent->left=new Node(val);

// Putting the statement on the same line as the condition
// makes it hard when stepping through with a de-bugger.
// If there was no else you would not be able to tell if the
// condition fired so split up the lines a bit.

// At a push if you really wanted to save space
if (val>parent->data)
{parent->right =new Node(val);}
else {parent->left  =new Node(val);}

// Personally I would use
if (val>parent->data)
{
parent->right =new Node(val);
}
else
{
parent->left  =new Node(val);
}

// Or K&R style
if (val>parent->data) {
parent->right =new Node(val);
}
else {
parent->left  =new Node(val);
}

}
//cout<<"fine2";
}
}


Not a fan of your brace style it is sloppy. This makes code hard to read and maintain. Also you use several different brace styles in your code. Pick a style and be consistent in its usage.

Looks like the code is correct.
Seems like you are mixing in tabs and spaces (which has made the indentation fail). When posting to websites it is usually a good idea to replace all tabs with spaces. Within your own code make sure you consistently use tabs and spaces (which is better is a religious war I am not going to get into).

Also you should start adding some white space to make the code more readable.

//Example:
if(p->left==NULL&&p->right==NULL){

// Why not make it easy to read:
if ((p->left == NULL) && (p->right == NULL)) {


There seems like there is a lot of repeated code here (BST::remove()) that can be factored out.

If I were to write this I would start with a recursive delete.

void BST::remove(valuetype val)
{
root = removeValue(root, val);
}
Node* BST::removeValue(Node* node, valuetype val)
{
if (val < node.data)
{
node.left  = removeValue(node.left, val);
return node;
}
else
{
node.right = removeValue(node.right, val);
return node;
}

}
{
Node*  result = NULL;

// We have found the node we want to remove.
if ((node.left == NULL) && (node.right == NULL))
{
delete node;
// Will return NULL
}
else if (node.right == NULL)
{
result = node.left;
delete node;
}
else if (node.left == NULL)
{
result = node.right;
delete node;
}
else
{
result = node;

// This is complicated.
// You should definately have a comment that explains the algorithm
// that you are using here.
Node* righty = findrightnode(node->left);
Node* parent = findparentforNode(righty->data);

node->data=righty->data;

if(parent != node) {
parent->right=righty->left;
}
else {
node->left=righty->left;
}
// You forgot to delete righty
delete righty;
}
return result;
}


In findNodebyvalue()
Again more white space needed.
Again tabs/space problem.
I would replace the if with a trinary operator.

//fins node with a value key
Node* BST::findNodebyvalue(valuetype key)
{
Node* p =root;
while((p != NULL) && (p->data != key))
{
p = (key < p->data) ? p->left : p->right;
}
return p;
}


In findparentforNode()
Again more white space needed.
Again tabs/space problem.

In your printing functions. Rather than serialize to std::cout. You should probably pass a reference to a stream onto which you want to serialize the tree.

The method custom print should probably be re-named breadth first print.

int main()
{
// Horrible indent.
BST tree;
tree.insert(10);
tree.insert(2);
tree.insert(4);
tree.insert(12);
tree.insert(23);
tree.traverse();
tree.custom_print();

// Wait for user to hit key.
getch();

// Can be replaced with:
std::string line;
std::getline(std::cin, line);

// Main is special.
// If you don't return a value the compiler plants a return 0; for you.
// Thus if your app is not going to report any errors to the OS it is