BST Insertion

[NoobProgrammer03]

hi, I'm having a problem in my binary search tree program

first of all, here's my class for binary tree and inside it is a class for each node
(Note: It's not complete yet)

class BST{
	private:
	class node{
		public:
		char data;
		node *left;
		node *right;

		node(){//constructor for each node
			left = NULL;
			right = NULL;
		}
	};
	node *root;//pointer to the root
	
	public:
	BST();
	void choices();
	void insert(node *key, char input);//insertion of a character
	void inorder(node *key);//inorder traversal output
};

and here's the code for the choices. the only choices available for now is insertion (the user input two characters: 'i' folowed by any character) and inorder traversal

void BST::choices(){
	char choice, choice2;

	cout << "[I -followed by a character-] Insertion of a Character" << endl
	     << "[TI] Inorder Traversal" << endl;
	cout << "Choose an option: "; cin >> choice; cin >> choice2;
	switch(toupper(choice)){
		case 'I': insert(root, toupper(choice2));
				  if(root==NULL) cout << "NULL" << endl; //for debugging purposes
				  break;
		case 'T': switch(toupper(choice2)){
					case 'I': inorder(root);
							  break;
				  }
				  break;
		default: cout << "***There's no such option!***" << endl;
				 break;
	}
}

the problem is... each time i insert a character, the root is always NULL :( i've been thinking that the problem lies in my insertion code

void BST::insert(node *key, char input){
	if(key==NULL){
		node *treePtr = new node;
		treePtr->data = input;
		key = treePtr;
	}
        /*additional question: is it right to do this instead?
        if(key==NULL){
                key = new node;
                key->data = input;
        }*/
	else if(input < key->data)
	    insert(key->right, input);
	else if(input > key->data)
	    insert(key->left, input);
	else
	    cout << "***The item is already in the tree!***" << endl;
}

but i really can't find the exact nest of the problem :( so please help me

also.. here's my code for inorder traversal, in case you need to see it

void BST::inorder(node *key){
	node *treePtr = key;
	if(treePtr==NULL)
	    cout << "***The tree is empty!***" << endl;
	else{
		inorder(treePtr->left);
		cout << treePtr->data << " ";
		inorder(treePtr->right);
	}
	cout << endl;
}

if you find other error/s in my code, pls tell me... i'll be more than thankful :)

tnx in advance ^_^

[cire]

Code outside of BST should not care about the internals of BST, so no public functions should take a pointer to a BST::node. Also, choices should not be a member of BST.

Consider the following:

#include <iostream>

class BST{
private:
    class node{
    public:
        char data;
        node *left;
        node *right;

        node(char ch) : data(ch), left(nullptr), right(nullptr) {}
    };
    node *root;//pointer to the root

    static void visit_inorder(const node*, void(*)(char)) ;
    static void insert(node*&n, char data);

public:
    BST() : root(nullptr) {}

    void insert(char data);

    // call a function for each element.
    void visit_inorder(void(*f)(char)) const { visit_inorder(root, f); }
};

void BST::insert(BST::node*& n, char data)
{
    if (data < n->data)
    {
        if (n->left)
            insert(n->left, data);
        else
            n->left = new node(data);
    }
    else if (data > n->data)
    {
        if (n->right)
            insert(n->right, data);
        else
            n->right = new node(data);
    }
}

void BST::insert(char data)
{
    if (root == nullptr)
        root = new node(data);
    else
        insert(root, data);
}

void BST::visit_inorder(const BST::node* n, void(*func)(char))
{
    if (!n)
        return;

    visit_inorder(n->left, func);
    func(n->data);
    visit_inorder(n->right, func);
}

void print_element(char element)
{
    std::cout << element << '\n';
}

int main()
{
    BST bst;
    bst.insert('P');
    bst.insert('B');
    bst.insert('Z');
    bst.insert('R');
    bst.insert('C');

    bst.visit_inorder(print_element);
}

http://ideone.com/csUAz4