This is my personal implementation of a binary search tree. My tree uses iteration instead of recursion for its insertion, deletion and searches for faster execution because function stack overhead is avoided. Recursion is still used for tree deletion because I didn’t want to implement a stack for the traversal of the tree which is required for deletion.

// SearchableADT test driver
// Copyright (C) 2011 Kyle Turley
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

// Purpose:
// this test driver is used to emperically test the performance of various
// searchable abstract data structures that adhere to the SearchableADT
// interface.

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include "BST.h"

using namespace std;

void menu_Loop(), menu_Choices(char ans);
void load_dict(), clr_dict(), find_a_word(), find_from_file(), tree_stats(), end_program();
bool isfound(string findme);

//declare a new SearchableADT to test
SearchableADT<string> *dictionary = new BST<string>;

int main() {

    menu_Loop();

    return 0;
}//end main

void menu_Loop() {
    char ans; //declare ans variable, this will be used OVER AND OVER
    do {
        cout << "--- ADT Tinkering Menu ---" << endl;
        cout << "1: Load a Dictionary File" << endl;
        cout << "2: Clear Dictionary" << endl;
        cout << "3: Check for an Entry" << endl;
        cout << "4: Check for Entries from File" << endl;
        cout << "5: Report Tree Statistics" << endl;
        cout << "6: Option 6 - Exit" << endl; //print us some options

        cin >> ans; //take in an answer
        cin.ignore(80, '\n'); 

        menu_Choices(ans);
    } while (ans != '6'); //keep on running on till they pick exit!
}// end menu_Loop()

void menu_Choices(char ans) {
    switch (ans)//roll thru options
    {
        case '1':
            load_dict();
            break;
        case '2':
            clr_dict();
            break;
        case '3':
            find_a_word();
            break;
        case '4':
            find_from_file();
            break;
        case '5':
            tree_stats();
            break;
        case '6':
            end_program();
            break;
        default://THEY DIDNT READ THE MENU, WHO WOULD HAVE THOUGHT?!?!
            cout << "Please read and follow all directions\n";
            break;
    }
}// end menu_Choices(char ans)

//functions, FILL WITH VALUABLE PROGRAMMING SKILLS

// Asks the user for a filename, then loads each whitespace delineated string into the SearchableADT
void load_dict() {

    string filename = "";
    fstream in;
    clock_t start, finish;
    while (!in.is_open()) {
        cout << "Enter a valid C++ file to Load" << endl;
        cin >> filename;
        in.open(filename.c_str());
    }
    start = clock();
    dictionary->loadFromFile(filename);
    finish = clock();
    in.close();
    cout << "## file added to ADT ##" << endl;
    cout << "Load time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}

// releases all memory occupied by the SearchableADT
void clr_dict() {
    clock_t start, finish;
    start = clock();
    dictionary->clear();
    finish = clock();
    cout << "## ADT CLEARED ##" << endl;
    cout << "time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}

// Asks the user for a word
void find_a_word() {
    string findme;
    cout << "Enter a string to search for" << endl;
    cin >> findme;

    clock_t start, finish;
    start = clock();
    // insert timing code here
    if(isfound(findme)){
        cout << "found it" << endl;
    }else
        cout << "not found" << endl;
    finish = clock();
    cout << "time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}

void find_from_file() {

    string filename = "";
    fstream in;
    clock_t start, finish;
    stringstream buffer;
    string temp;
    int misspelled_count = 0;

    while (!in.is_open()) {
        cout << "Enter a valid Text file to Read" << endl;
        cin >> filename;
        in.open(filename.c_str());
    }

    buffer << in.rdbuf();
    in.close();
    start = clock();
    // attempt to find each word
    while (buffer.good()) {
        buffer >> temp;
        if(!isfound(temp)){
            cout << temp << " isn't in the dictionary" << endl;
            misspelled_count++;
        }
    }
    finish = clock();
    cout << misspelled_count << " misspelled words were found" << endl;
    cout << "Search time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}

void tree_stats() {
    clock_t start, finish;
    start = clock();
    cout << "Number of Entries: " << dictionary->numEntries() << endl;
    finish = clock();
    cout << "Report time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}

bool isfound(string findme){
    bool isfound = false;
    string alphabet = "abcdefghijklmnopqrstuvwxyz";

    // make findme lowercase
    for (int i = 0; i < strlen(findme.c_str()); i++) {
        if (findme[i] >= 0x41 && findme[i] <= 0x5A)
            findme[i] = findme[i] + 0x20;
    }

    //if findme contains a ? character, generate a list of 26 possibilities to search for
    if (findme.find_first_of('?') != string::npos) {
        string possibilities[25];
        int qmarkindex = findme.find_first_of('?');

        for (int i = 0; i < 25; i++) {
            possibilities[i] = findme.replace(qmarkindex, 1, 1, alphabet[i]);
            if (dictionary->isThere(possibilities[i])){
                cout << possibilities[i] << endl;
                isfound = true;
            }
        }
    } else // no '?' character was found,
        isfound = dictionary->isThere(findme);
    return isfound;
}

void end_program(){
	dictionary->clear(); // release memory stored by the dictionary
	exit(0);
}

// Abstract Searchable ADT interface
// Copyright (C) 2011 Kyle Turley
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef SEARCHABLEADT_H
#define SEARCHABLEADT_H

#include <string>

using namespace std;

template <typename T>
class SearchableADT{
public:
	// these are all purely virtual functions that must be implemented by all classes that inherit from SearchableADT().
	virtual int loadFromFile(string filename) = 0;
	virtual void clear(void) = 0;
	virtual void insertEntry(T value) = 0;
	virtual void deleteEntry(T value) = 0;
	virtual bool isThere(T value) = 0 ;
	virtual int numEntries(void) = 0;

private :
	//no private methods or data members.

};

#endif

// BST class
// Copyright (C) 2011 Kyle Turley
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef BST_H
#define BST_H
#pragma once

#include "SearchableADT.h"
#include <cstring>

using namespace std;

template <typename T>
class binarynode {
public:
    T data;
    binarynode<T> *left;
    binarynode<T> *right;
};

template <typename T>
class BST : public SearchableADT<T> {
public:
    BST(void);
    ~BST(void);
    int loadFromFile(string filename);
    void clear(void);
    void insertEntry(T value);
    void deleteEntry(T value);
    bool isThere(T value);
    int numEntries(void);

    // additional methods, not part of abstract interface
    void postorder_delete(binarynode<T>* itr);
    int BST<T>::height(binarynode<T>* itr);

private:
    binarynode<T> * root_ptr;
    double numnodes;

};

template <typename T>
BST<T>::BST(void) {
    root_ptr = NULL;
    numnodes = 0;
}

template <typename T>
BST<T>::~BST(void) {
    this->clear();
}

template <typename T>
int BST<T>::loadFromFile(string filename) {

    fstream in;
    vector<T> vect;
    vector<T>::const_iterator iter;
    std::stringstream buffer;
    string temp;

    in.open(filename.c_str());
    buffer << in.rdbuf();

    // read each word into a vector
    while (buffer.good()) {
        buffer >> temp;
        vect.push_back(temp);
    }
    // randomize the vector for more efficient inserts
    // just in case the user tries to input a sorted file.
    // "A good programmer looks both ways before crossing a one way street"
    srand(time(0));
    random_shuffle(vect.begin(), vect.end());

    //now insert each randomized entry into the BST
    for (iter = vect.begin(); iter != vect.end(); ++iter) {
        //cout << *iter << endl;
        this->insertEntry(*iter);
    }

    return 0;
}

template <typename T>
void BST<T>::clear(void) {
    this->postorder_delete(root_ptr);
    root_ptr = NULL;
    //numnodes = 0;
    return;
}

template <typename T>
void BST<T>::insertEntry(T value) {

    // create the new node to be inserted and populate it with data
    binarynode<T> *temp, *prev, *curr;
    temp = new binarynode<T>;
    temp->data = value;
    temp->left = NULL;
    temp->right = NULL;

    // insert the node into its proper place in the tree
    if (root_ptr == NULL) {
        // the tree is empty so make the new node the root
        root_ptr = temp;
    } else {
        // discover the new nodes proper place in a binary search fashion
        curr = root_ptr;
        while (curr != NULL) {
            prev = curr;
            if (temp->data < curr->data)
                curr = curr->left;
            else
                curr = curr->right;
        }
        // the proper place has been found at this point.  insert the new node
        if (temp->data < prev->data)
            prev->left = temp;
        else
            prev->right = temp;
    }
    numnodes++;
    return;
}

template <typename T>
void BST<T>::deleteEntry(T value) {

    binarynode<T> *prev, *curr, *grandparent;
    prev = curr = grandparent = NULL;

    binarynode<T> *deleteme = new binarynode<T>;
    deleteme->data = value;

    // discover where the node should be in a binary search fashion
    curr = root_ptr;
    while (curr != NULL) {
        grandparent = prev;
        prev = curr;
        if (deleteme->data < curr->data)
            curr = curr->left;
        else if (deleteme->data > curr->data)
            curr = curr->right;
        else
            break;
    }
    if (deleteme->data == prev->data) {// found it, now delete it. There are special cases for different children
        if (prev->left == NULL && prev->right == NULL) { //no children
            if (grandparent->left->data == prev->data)
                grandparent->left = NULL;
            else
                grandparent->right = NULL;
            delete prev;
        } else if (prev->left == NULL && prev->right != NULL) { //right child exists
            if (grandparent->left->data == prev->data)
                grandparent->left = prev->right;
            else
                grandparent->right = prev->right;
            delete prev;
        } else if (prev->left != NULL && prev->right == NULL) { //left child exists
            if (grandparent->right->data == prev->data)
                grandparent->right = prev->left;
            else
                grandparent->left = prev->left;
            delete prev;
        }
    }
    numnodes--;
}

template <typename T>
bool BST<T>::isThere(T value) {
    binarynode<T> *prev, *curr;

    curr = root_ptr;

    // find the right spot in an iterative fashion
    // recursion should be avoided whenever possible for safety and performance
    while (curr != NULL) {
        prev = curr;
        if (value < curr->data)
            curr = curr->left;
        else if (value > curr->data)
            curr = curr->right;
        else if (prev->data == value)
            return true; // value was found
    }
    return false; //value wasn't found
}

template <typename T>
int BST<T>::numEntries(void) {
    // do a post-order traversal counting along the way
    // this is kinda hacked, but I want to preserve the given SearchableADT interface

    cout << "Tree Height: " << height(root_ptr) << endl;

    return numnodes;
}

template <typename T>
void BST<T>::postorder_delete(binarynode<T>* itr) {
    if (itr != NULL) {
        postorder_delete(itr->left);
        postorder_delete(itr->right);
        delete itr;
        numnodes--;
    }
    return;
}

template <typename T>
int BST<T>::height(binarynode<T>* itr) {
    if (itr == NULL)
        return -1;
    else
        return 1 + max(height(itr->left), height(itr->right));
}

#endif