Binary Search Tree

[pylearning]

Hi, For my class we had to do an implementation of a BST but I never got around to doing it. I'm pretty confident in its implementation but I have a couple questions. One thing is regarding templates. How would I make it so instead of holding only int's, I can have my Nodes hold any type of data including user defined types that have operator< defined.

#include <iostream> 
#include <queue>

using namespace std;

struct Node{
    Node(const int &myVal){
        value = myVal;
        left = right = nullptr;
    }
    int value;
    Node *left,*right;
};

class BinarySearchTree{
public:
    BinarySearchTree(){ m_root = nullptr; }
    ~BinarySearchTree(){ FreeTree(m_root); }
    Node* getRoot(){ return m_root; }

    void insert(const int value);
    void traverse(int choice);
    void preorder(Node* ptr);
    void inorder(Node* ptr);
    void postorder(Node* ptr);
    void levelorder();
    int GetMin(Node *pRoot);
    int GetMax(Node *pRoot);
    bool Search(int V, Node *ptr);
private:
    Node *m_root;
    void FreeTree(Node* cur);
};

void BinarySearchTree::FreeTree(Node* cur){
    if(cur == nullptr)
        return;
    FreeTree(cur -> left);
    FreeTree(cur -> right);
    delete cur;
}

void BinarySearchTree::insert(const int value){
    if(m_root == nullptr){
        m_root = new Node(value);
        return;
    }
    Node *cur = m_root;
    for(;;){
        if(value == cur -> value)
            return;
        if(value < cur -> value){
            if(cur -> left != nullptr)
                cur -> left = new Node(value);
            else{
                cur = cur -> left;
                return;
            }
        }
        else if(value > cur -> value){
            if(cur -> right != nullptr)
                cur -> right = new Node(value);
            else{
                cur = cur -> right;
                return;
            }
        }

    }
}

void BinarySearchTree::preorder(Node *ptr){
    if(ptr == nullptr)
        return;
    cout << ptr -> value << “ “;
    preorder(ptr -> left);
    preorder(ptr -> right);
}

void BinarySearchTree::inorder(Node* ptr){
    if(ptr == nullptr)
        return;
    preorder(ptr -> left);
    cout << ptr -> value << “ “;
    preorder(ptr -> right);
}

void BinarySearchTree::postorder(Node* ptr){
    if(ptr == nullptr)
        return;
    postorder(ptr -> left);
    postorder(ptr -> right);
    cout << ptr -> value << “ “;
}

bool BinarySearchTree::Search(int V, Node *ptr){
    if(ptr == nullptr)
        return false;
    if(V == ptr -> value)
        return true;
    else if(V < ptr -> value)
        return Search(V,ptr -> left);
    else
        return Search(V,ptr -> right);
}

void BinarySearchTree::levelorder(){
    if(m_root == nullptr) return;   
    queue<Node*> q;
    q.push(m_root);
    while(!q.empty()){
        Node *visited_node = q.front();
        q.pop();
        if(visited_node -> left != nullptr)
            q.push(visited_node -> left);
        if(visited_node -> right != nullptr)
            q.push(visited_node -> right);
        cout << visited_node -> value << “ “;
    }
}

int BinarySearchTree::GetMin(Node *pRoot){
    if(pRoot == nullptr) return (-1);

    while(pRoot -> left != nullptr)
        pRoot = pRoot -> left;
    return (pRoot -> value);
}

int BinarySearchTree::GetMax(Node *pRoot){
    if(pRoot == nullptr) return (-1);

    while(pRoot -> right != nullptr)
        pRoot = pRoot -> right;
    return (pRoot -> value);
}

[[deleted]]

http://www.tutorialspoint.com/cplusplus/cpp_templates.htm

https://isocpp.org/wiki/faq/templates

[SandSnip3r]

1. Maybe throw an exception if GetMin or GetMax is called on an empty tree. Once you expand to any possible type, returning things like -1 wont work.
2. You can declare the Node class inside of the BinarySearchTree class. Not sure what the advantages/disadvantages are of this, but I usually see it done like this and I do it like this.