Binary Search Tree Optimization

[funprogrammer]

I was working on binary tree implementation and came up with this implementation. Can someone help me optimize this code?

/*
Binary Search Tree(BST)
06/27/2013
*/
#include "iostream"
#include "vector"
#include "conio.h"
using namespace std;

class node{
public:
   int data;
   node* ltree;
   node* rtree;

   node(int x){
      data = x;
      ltree = NULL;
      rtree = NULL;
   }
   node(int x, node* node1, node* node2){
      data = x;
      ltree = node1;
      rtree = node2;
   }

   ~node(){};
};
class BST{
public:
   node* root;

   BST(){
      root = NULL;
   }
   node* newNode(int x){
	   node* Node1 = new node(x);
	   return Node1;
   }
   node* insertNode(int x, node* n1);
};

node* BST::insertNode(int x, node* n1){
   if(n1 == NULL){
     n1 = newNode(x);
   }
   else{
      if(x <= n1->data){
	     n1->ltree = insertNode(x,n1->ltree);
      }
      else if(x > n1->data){
	     n1->rtree = insertNode(x,n1->rtree);
	  }
   }
   return n1;
}

int main(){
   BST BT1;
   BT1.root = BT1.insertNode(4,BT1.root);
   BT1.root = BT1.insertNode(5,BT1.root);
   getch();
}

[ENIGMAx]

If you want my two cents (for what they're worth) I believe you should have a class called BinaryTree, BinarySearchTree, or whatever you'd like to call it, which utilizes a node struct as a member. The only node you need the class to keep track of specifically as a member is the root. Which is just a pointer to the said 'root'. That's how I remember being taught for BSTs.

You'd just define the node as a struct object with the data, left pointer and right pointer. The class then has methods to insert and remove nodes and any other things you'd like such as sorting (if it happens to be a binary search tree or binary heap). Its root node is all you need as a part of the class itself (being a private member) and all other nodes in the BT are added, removed, or accessed via pointer operations in internal methods.

I'd have an external struct definition with something like:

typedef struct node
{
	int data;
	Node* LeftNode;
	Node* RightNode;
} Node;

You can ignore my use of typedef all the time, you could just as well use "node" here.

Then declare the root inside the class's private members. Using a node pointer for the root will be beneficial when traversing the tree with pointers recursively.
Include in the private section Node* root; for a pointer to the root node.

[funprogrammer]

Good point ENIGMAx. I am confused on this point. I was thinking it is okay to use class for node, but I am interested to know what is the standard followed? Do we have to use struct data structure for node? Is there a good book or documentation which explains this?

Also, when I run the program, the leaf nodes have "?????" for data,ltree and rtree members. I dont know if this is correct implementation or needs improvement.Any suggestions or improvements?

   BT1	{root=0x00761330 }	BST
      root	0x00761330 {data=4 ltree=0x00000000 rtree=0x00761378 }	node *
      data	4	int
      ltree	0x00000000 {data=??? ltree=??? rtree=??? }	node *
      rtree	0x00761378 {data=5 ltree=0x00000000 rtree=0x00000000 }	node *
          data	5	int
          ltree	0x00000000 {data=??? ltree=??? rtree=??? }	node *
             data	CXX0030: Error: expression cannot be evaluated	
             ltree	CXX0030: Error: expression cannot be evaluated	
             rtree	CXX0030: Error: expression cannot be evaluated	
          rtree	0x00000000 {data=??? ltree=??? rtree=??? }	node *
             data	CXX0030: Error: expression cannot be evaluated	
             ltree	CXX0030: Error: expression cannot be evaluated	
             rtree	CXX0030: Error: expression cannot be evaluated	

[ENIGMAx]

I don't think I'm going out on a limb by saying that a result like you posted isn't the right output. I'm at work right now taking a little break so I don't have enough time to paste your code into a project and debug it, or even look at it too closely for that matter.

But another thing of note that stood out to me was a missing destructor for your tree. With BSTs you have a lot of pointers and should be destroying your tree node-by-node via recursion. You can make a function that is called by the destructor for that.

While you don't NEED to have a struct for a node, I think it makes more sense honestly. A node doesn't need to allocate or deallocate its own memory (hence constructors or destructors), it doesn't have methods, etc. which really just lends itself to a struct (only needs data members). But I believe you can do it either way...

There are some great books and articles out there that can cover this if you don't have an instructor in-person. A quick search on Google brought up this article: http://www.cprogramming.com/tutorial/lesson18.html, and it turns out it's by Alex Allain who's a great teacher (with both explanations and examples) of C++ topics. Looking through there just now real quick helped refresh my memory and I'm pretty sure he runs through the full implementation of a basic BST.

Feel free to ask more questions, however I believe that article will probably answer most of them. Good luck!