Template Binary Search Tree This is a simple binary search tree implementation written with C++'s templates feature I wrote to learn C++. What improvements would make this cleaner and better as far as C++ practices go, and are there any problems with implementing the algorithm?

#include &lt;iostream&gt;
#include &lt;string&gt;

using namespace std;


template &lt;class T, class V&gt;
class BinarySearchTree {

    struct t_node {
        t_node * parent;
        t_node * left;
        t_node * right;

        T data;
        V value;
        // Sorted by Value
    };

    t_node * root;

    t_node* getMin() {
        return getMin(root);
    }
    t_node* getMin(t_node * x) {
        while (x-&gt;left !=nullptr) {
            x = x-&gt;left;
        }
        return x;
    }

    t_node* getMax() {
        t_node * x = root;
        while (x-&gt;right != nullptr) {
            x = x-&gt;right;
        }
        return x;
    }

    t_node* sucessor(t_node* x) {
        if (x-&gt;right != nullptr) {
            return getMin(x-&gt;right);
        }
        t_node * y = x-&gt;parent;
        while (y!=nullptr &amp;&amp; x==y-&gt;right) {
            x = y;
            y = y-&gt;parent;
        }
        return y;
    }

public:

    void inOrderTreeWalk() {
        inOrderTreeWalk(root);
    }

    // Needs Stream Overload on template T type to work.
    void inOrderTreeWalk(t_node * x) {
        if (x != nullptr) {
            inOrderTreeWalk(x-&gt;left);
            cout &lt;&lt; x-&gt;data;
            inOrderTreeWalk(x-&gt;right);
        }
    }

    T search(V keyword) {
        t_node * x = root;
        while (x!=nullptr &amp;&amp; keyword != x-&gt;value) {
            if (keyword &lt; x-&gt;value) {
                x = x-&gt;left;
            }
            else x = x-&gt;right;
        }
        return x-&gt;data;
    }

    void insert(V keyword, T object) {
        // Create t_node;
        t_node * z = new t_node;
        z-&gt;value = keyword;
        z-&gt;data = object;


        t_node * y = nullptr;
        t_node * x = root;

        while (x!= nullptr) {
            y = x;
            if (z-&gt;value &lt; x-&gt;value) {
                x = x-&gt;left;
            }
            else x = x-&gt;right;
        }
        z-&gt;parent = y;
        if (y == nullptr) {
            root = z;
        } else if (z-&gt;value &lt; y-&gt;value) {
            y-&gt;left = z;
        } else y-&gt;right = z;
    }
};


// Demo Code
int main(int argc, const char * argv[]) {


    string Charles = "Charles Finny";
    string CharlesD = "Personal Assistant";
    string Bob = "Bob of Yorkshire";
    string BobD = "Unkown";
    string Sam = "Sam Smith";
    string SamD = "Programmer";
    string Mary = "Mary Jane";
    string MaryD = "Manager";

    BinarySearchTree&lt;string, string&gt; EmployeeRecords;
    EmployeeRecords.insert(Charles, CharlesD);
    EmployeeRecords.insert(Bob, BobD);
    EmployeeRecords.insert(Sam, SamD);
    EmployeeRecords.insert(Mary, MaryD);

    string result = EmployeeRecords.search("Sam Smith");
    cout &lt;&lt; result &lt;&lt; "\n" ;
    EmployeeRecords.inOrderTreeWalk();



    return 0;
}
Memory Handling

I see new but I don't see delete. Your tree leaks memory. It needs to clean up after itself in a destructor. And once you add that, you get into the Rule of Three: you need to add the copy constructor and the copy assignment operator, otherwise you'd still leak when you copy your tree.

Usage

Your code looks like an implementation of std::map, and your usage suggests the same, so it'd be better to change your template arguments from T and V (which mean nothing) to Key and Value. Using value as the key is confusing - you should name it key. Although conventionally nodes for maps in the C++ standard library use std::pair&lt;const Key, Value&gt;s. 

You should make it clear that Key needs to be both LessThanComparable and EqualityComparable, or provide ways of passing comparators in as template arguments.

If I try to search() for something not in the map, x will eventually become nullptr and then you return x-&gt;data. Oops! 

You can insert elements with duplicate values. Is that intentional?

inOrderTreeWalk should be spelled std::ostream&amp; operator&lt;&lt;(std::ostream&amp;, const BinarySearchTree &amp;). 

Other


Avoid using namespace std;, especially in headers. 
Take your arguments by reference to const to avoid having to deal with copies.
You should support erasing elements.
You should look into various balancing algorithms for you tree so that if I insert 1 then 2 then 3 then 4 then 5, I don't end up with linear-time search. 
return 0; from main() is implied, you don't need to explicitly provide it.