I would love some input on my BST tree.

Hello. I have spent some time working on my BST tree and have finally gotten it to work. I was wondering if some people could take a look at my code and perhaps offer some criticism.
I would really appreciate it. Thank you.

Code:

---

//======================
// BST.h
//======================

struct node
{
        int element;
        node * left;
        node * right;
};

// My BST class
class BST
{

public:
       
        BST();
        ~BST();
        void insert();
        void remove();
        void display();

private:

        node * root;
        int num_in_tree;

        void insert(int, node *&);
        int remove(int, node *&);
        node * inorderSuccessor(node *&);
        int children(node *);
        void display(node *);
        void destroy(node *&);
};

//=============
// BST.cpp
//=============

#include <iostream>
#include "BST.h"

using namespace std;

BST::BST()
{
        root = NULL;
        num_in_tree = 0;
}

BST::~BST()
{
        destroy(root);
}

//================================================
// INPUT: none
// OUTPUT: none
// gets input from user and calls recursive insert
//================================================
void BST::insert()
{
        int key;
        cout << "Enter a number to insert:\n";
        cin >> key;
        cin.get();
        insert(key, root);
}

//================================================
// INPUT: none
// OUTPUT: none
// gets input from user and calls recursive remove
//================================================
void BST::remove()
{
        int key;
        cout << "Enter a number to remove\n";
        cin >> key;
        cin.get();
        if(remove(key, root) == 1)
                cout << "Number not found.\n";
}

//============================================
// INPUT: none
// OUTPUT: none
// wrapper function for display
//============================================
void BST::display()
{
        display(root);
}

//============================================
// INPUT: pointer to a node
// OUTPUT: none
// recursively inserts a new node into the BST
//============================================
void BST::insert(int newElement, node *& troot)
{
        if(!troot)
        {
                troot = new node;
                troot->element = newElement;
                troot->left = NULL;
                troot->right = NULL;
                ++num_in_tree;
        }
        else if(newElement < troot->element)
        {
                insert(newElement, troot->left);
        }
        else
        {
                insert(newElement, troot->right);
        }
}

//================================================
// INPUT: pointer to a node
// OUTPUT: 1 if element to be deleted is not found
//                  0 if element is successfully deleted
//================================================
int BST::remove(int oldElement, node *& troot)
{
        if(!troot)
        {
                return 1;  //error code
        }
        else if(oldElement < troot->element)
        {
                remove(oldElement, troot->left);
        }
        else if(oldElement > troot->element)
        {
                remove(oldElement, troot->right);
        }
        else if(children(troot) == 2)
        {
                troot->element = inorderSuccessor(troot->right)->element;
                remove(troot->element, troot->right);
        }
        else
        {
                if(troot->left)
                {
                        troot->element = troot->left->element;
                        remove(troot->element, troot->left);
                }
                else if(troot->right)
                {
                        troot->element = troot->right->element;
                        remove(troot->element, troot->right);
                }
                else
                {
                        node * oldNode = troot;
                        troot = NULL;
                        delete oldNode;
                        return 0;
                        --num_in_tree;
                }
        }
}

//=========================================
// INPUT: pointer to a node
// OUTPUT: pointer to the inorder successor
//        of the input node
//=========================================
node * BST::inorderSuccessor(node *& troot)
{
        if(!troot->left)
        {
                return troot;
        }
        else
        {
                inorderSuccessor(troot->left);
        }
}

//==================================
// INPUT: pointer to a node
// OUTPUT: 0 if node has no children
//                  1 if node has 1 child
//        2 if node has 2 children
//==================================
int BST::children(node * troot)
{
        if(troot->left && troot->right)
        {
                return 2;
        }
        else if(troot->left || troot->right)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

//=========================================
// INPUT: pointer to a node
// OUTPUT: contents of tree in sorted order
// recursively prints contents of the BST
//=========================================
void BST::display(node * troot)
{
        if(troot)
        {
                display(troot->left);
                cout << troot->element << endl;
                display(troot->right);
        }
}

//================================
// INPUT: pointer to a node
// OUTPUT: none
// recursively deletes the BST
//================================
void BST::destroy(node *& troot)
{
        if(troot)
        {
                destroy(troot->left);
                destroy(troot->right);
                delete troot;
        }
        troot = NULL;
}

---

Code:

---

        void insert();
        void remove();
        void display();

---

Not to useable interface in any real application. No application want your class interact directly with the user. Your class should represent a Tree, should provide methods to work with the tree, should be fully independend from the input method. If I take this class and want to fill it from the file - I fail, If I want to provide some GUI for user convinience - I fail, this class is unusable.

You should remove all connection to <iostream> from your class

Code:

---

return 0;
--num_in_tree;

---

strange sequence of commands

don't you get warning that not all paths in the BST::remove(int oldElement, node *& troot)
return values?

And why not to make it a little more generic making it a template replacing

int element;
by
T element;?

I couldn't help but notice that you never destroy from anywhere but the root.

Code:

---

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

template <class T> class BST
{
public:   
        BST();
        ~BST();
        //display(node<T> * = root); 
            // -- consider returning an std::string or having it take a stream reference as a parameter
        void destroy(node<T> *& troot = root);
        void insert(T newElement, node<T> *& troot = root);
        int remove(T oldElement, node<T> *& troot = root);
        const int population() { return num_in_tree; }
private:
        node<T> * root;
        int num_in_tree;
        node<T> * inorderSuccessor(node<T> *& troot);
        int children(node<T> * troot);
     
};

---

Quote:

---

Originally Posted by CodeMonkey

I couldn't help but notice that you never destroy from anywhere but the root.

---

Incorrect.
The recursive calls that pass in troot->left and troot->right, actually modify troot->left and troot->right, and being that they are the root of their own subtree it can delete from anywhere.
I'm not saying the the rest of the function is totally correct though.

I appreciate you taking the time to look at it guys. You've given me some areas I can improve on. Thanks.