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
#include
#include
#include
#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)
{
//coutparent->data) parent->right=new Node(val);
else parent->left=new Node(val);
}
//coutleft==NULL&&p->right==NULL){
if(p!=root){
Node* parent= findparentforNode(val);
if(valdata) 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(valdata) parent->left=p->left;
else parent->right=p->left;
}
else root

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

#include

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

This is non standard (MS-DOS specific)

#include

// 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);
};

Remove useless comments.

//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.

So you need to add the following methods to your class:

~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.
//coutparent->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
{
pare

StackExchange Code Review Q#17864, answer score: 23