Template Binary Search Tree

Question

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 <iostream>
#include <string>

using namespace std;


template <class T, class V>
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->left !=nullptr) {
            x = x->left;
        }
        return x;
    }

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

    t_node* sucessor(t_node* x) {
        if (x->right != nullptr) {
            return getMin(x->right);
        }
        t_node * y = x->parent;
        while (y!=nullptr && x==y->right) {
            x = y;
            y = y->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->left);
            cout << x->data;
            inOrderTreeWalk(x->right);
        }
    }

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

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


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

        while (x!= nullptr) {
            y = x;
            if (z->value < x->value) {
                x = x->left;
            }
            else x = x->right;
        }
        z->parent = y;
        if (y == nullptr) {
            root = z;
        } else if (z->value < y->value) {
            y->left = z;
        } else y->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<string, string> EmployeeRecords;
    EmployeeRecords.insert(Charles, CharlesD);
    EmployeeRecords.insert(Bob, BobD);
    EmployeeRecords.insert(Sam, SamD);
    EmployeeRecords.insert(Mary, MaryD);

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



    return 0;
}

Answer 1

Add the following to the suggestions made by Barry in his answer.

Add constructors to t_node

They make sure that all the member variables are initialized properly.

struct t_node {

   // Default constructor
   t_node () : parent(nullptr), left(nullptr), right(nullptr), data(), value() {}

   // Constructor with data.
   t_node (T d, V v) : parent(nullptr), left(nullptr), right(nullptr), data(d), value(v) {}

    t_node * parent;
    t_node * left;
    t_node * right;

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

Add default constructor, copy constructor, and copy assignment operator

See The Rule of Three for issues that need to be dealt with when your class uses dynamic memory allocation.

With your posted code, the member variable root remains uninitialized when you construct an instance of BinarySearchTree. In theory, your code is subject to undefined behavior. With a default constructor, you can make sure that root is initialized properly -- most likely to nullptr.

getMin() has the potential to access nullptr

You have:

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

When the object is empty and root is initialized to nullptr, you will end up accessing x->left with value of x being nullptr. That is cause for undefined behavior.

I suggest

t_node* getMin() {
    if (root)
       return getMin(root);
    else
       return nullptr;
}

Make getMax() similar to getMin()

Add

t_node* getMax() {
    if (root)
       return getMax(root);
    else
       return nullptr;
}

Do not pollute your class with cout

Change inOrderTreeWalk to take a functor as an argument. Call the functor for every item of the BinarySearchTree.

template <typename F>
void inOrderTreeWalk(F f) {
    inOrderTreeWalk(root, f);
}

template <typename F>
void inOrderTreeWalk(t_node * x, F f) {
    if (x != nullptr) {
        inOrderTreeWalk(x->left, f);
        f(x->data);
        inOrderTreeWalk(x->right, f);
    }
}

And now, you can use it as:

EmployeeRecords.inOrderTreeWalk([](std::string const& s) { std::cout << s << std::endl;} );

Answer 2

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<const Key, Value>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->data. Oops!

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

inOrderTreeWalk should be spelled std::ostream& operator<<(std::ostream&, const BinarySearchTree &).

Other

1. Avoid using namespace std;, especially in headers.
2. Take your arguments by reference to const to avoid having to deal with copies.
3. You should support erasing elements.
4. 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.
5. return 0; from main() is implied, you don't need to explicitly provide it.