Thread: binary search tree with templates

Hi.I am trying to implement BST using templates.
This is the code that i have written.

Code:

template <class T>
struct node
{
	struct node *left;
	T info;
	struct node *right;
};

node<int>* root;

template <class T>
class bst
{
	public:		
	void insert(node<T> *,node<T> *);
	void inorder(node<T> *);
};

template <class T>
void bst<T> :: insert(node<T> *tree,node<T> *newnode)
{
	if(root == NULL)
	{		
		T num;
		cout << "Enter element\n";
		cin >> num;
		newnode->info = num;
		root = new node<int>;
		root->info = newnode->info;
		root->left = NULL;
		root->right = NULL;
		cout << "Root element has been added\n";
		return;
	}
	if(tree->info == newnode->info)
	{
		cout << "Element already exists\n";
		return;
	}
	if(newnode->info < tree->info)
	{
		if(tree->left != NULL)
			insert(tree->left,newnode);
		else
		{
			cout << "Enter element\n";
		    cin >> newnode->info;
			tree->left = newnode;
			newnode->left = NULL;
			newnode->right = NULL;
			cout << "Element added to the left\n";
			return;
		}
	}
	else
	{
		if(tree->right != NULL)
			insert(tree->right,newnode);
		else
		{
			cout << "Enter element\n";
		    cin >> newnode->info;
			tree->right = newnode;
			newnode->left = NULL;
			newnode->right = NULL;
			cout << "Element added to the right\n";
			return;
		}
	}
}


int main()
{
	int option;
	bst<int> B;
	node<int> *temp;
 B.insert(root,temp);
}

There are no errors but the program hangs.
What is the mistake with this program ?

Code:

// Narendrav,

// Your program doesn't hang for me, but since it does have *undefined behavior* it might hang in some cases.
// Let's go through it.

// You need to include some files for declarations (just to get your code to compile):

#include <cstddef> // For NULL
#include <iostream> // for std::cout and std::cin

// All references to cout and cin need to have namespace specifications (std::) to get your code to compile.


template <class T>
struct node
{
    struct node *left;
    T info;
    struct node *right;
// No parent node pointer? That is okay.
};

// As laserlight said, you don't want a global variable for this. Probably put this in bst?

node<int>* root;

template <class T>
class bst
{
    public:

// Some doc here to explain what these parameters are would be good.
// Is the first parameter the root node? Probably better to make that a member.
// Is the second parameter the node to insert?
// Does the tree take ownership of the node?
// Does it make a copy?
// Documentation makes life better for you, for your code reviewers and for your library users.
// In this case it is critical to understanding the problems with your code. In your main() routine
// You are passing in a 

    void insert(node<T> *,node<T> *);

// I don't see this and it isn't clear what it would do.
    void inorder(node<T> *);
};

template <class T>
void bst<T> :: insert(node<T> *tree,node<T> *newnode)
{
    if(root == NULL)
    {
// Since T is a templated type, how do you know it is a number? Could it be a string?
// Why are we creating a T anyway. This function is an insert function, so why is it doing this?

        T num;

// Your type shouldn't be writing to std::cout in the middle of an insert. It make your type
// unusable in a lot of contexts and it isn't a logical requirement of an insert.

        std::cout << "Enter element\n";

// Ditto with reading in the middle of an insert.

        std::cin >> num;

// You are writing over the value in newnode. Why did you pass it in if you are just going to overwrite it?

// With the main() routine that you have below, you are passing in newnode as a pointer that is never initialized.
// Here you are dereferencing your uninitialized pointer. This is *undefined behavior* meaning that anything can
// happen, including hanging your machine.

        newnode->info = num;
        root = new node<int>;
        root->info = newnode->info;
        root->left = NULL;
        root->right = NULL;
        std::cout << "Root element has been added\n";
        return;

// Were we supposed to take ownership of the pass in node? If so we just leaked it.
// If not we changed its value, but didn't use it which may be a surprise to the caller.


    }
    if(tree->info == newnode->info)
    {

// Probably better to either throw or return an error. Writing to the console
// means that:
//   Your library can't be used in a lot of contexts
//   There is no way for the calling code to detect this issue.

        std::cout << "Element already exists\n";
        return;
    }
    if(newnode->info < tree->info)
    {
        if(tree->left != NULL)
            insert(tree->left,newnode);
        else
        {

// This code has many of the same issues as the code above. In fact it should be refactored
// as a function called from both places.

            std::cout << "Enter element\n";
                std::cin >> newnode->info;
            tree->left = newnode;
            newnode->left = NULL;
            newnode->right = NULL;
            std::cout << "Element added to the left\n";
            return;
        }
    }
    else
    {
        if(tree->right != NULL)
            insert(tree->right,newnode);
        else
        {
            std::cout << "Enter element\n";
                std::cin >> newnode->info;
            tree->right = newnode;
            newnode->left = NULL;
            newnode->right = NULL;
            std::cout << "Element added to the right\n";
            return;
        }
    }
}


int main()
{

// "option" isn't used at all.

    int option;
    bst<int> B;
    node<int> *temp;
        B.insert(root,temp);
}

// Narendrav, Make another pass at this code thinking about the issues that laserlight and I have raised.

// Consider a main that might look like this:

int main()
{
    bst<int> b;
    b.insert(10); // root value
    b.insert(15);
    b.insert(5);
    assert(b.contains(5) && b.contains(10) && b.contains(15));
}