Simple binary search tree implementation using templates. Depends on my list.h gist (https://gist.github.com/danicat/7049073).

tree.h

#ifndef DANI_SIMPLE_TREE_H_
#define DANI_SIMPLE_TREE_H_

/*
  Simple Binary Search Tree generic implementation using templates.

  Depends: list.h (see github for newest version).

  Author: Daniela Petruzalek (https://gist.github.com/danicat)
  Date  : October, 20th 2013
*/

#include <iostream>

#include "list.h"

namespace dani {

template <class T>
class Node {
 public:
  Node(const T& value) : data_(value), left_(NULL), right_(NULL) {}
  ~Node() {}

  const T&  GetValue() const { return data_; }
  void      SetLeft(Node* left) { left_ = left; }
  Node*     GetLeft() const { return left_; }
  void      SetRight(Node* right) { right_ = right; }
  Node*     GetRight() const { return right_; }

  void      Print() const { std::cout << data_ << std::endl; }

 private:
  Node();

  T     data_;
  Node* left_;
  Node* right_;
};

template <class T>
class BinarySearchTree {
 public:
  BinarySearchTree() : root_(NULL) {}
  ~BinarySearchTree();

  bool Insert(const T& value);

  Node<T>* GetRoot() const { return root_; }

  Node<T>* Find(Node<T>* root, const T& value) const;

  int  Height(Node<T>* root) const;

  void PrintPreOrder (Node<T>* root) const; // Parent, Left, Right
  void PrintInOrder  (Node<T>* root) const; // Left, Parent, Right
  void PrintPostOrder(Node<T>* root) const; // Left, Right, Parent

  void PrintBreadthSearchFirst() const;

 private:
  void InsertNode(Node<T>* root, Node<T>* ins);
  void DeleteNode(Node<T>* node);

  Node<T>* root_;
};

template <class T>
BinarySearchTree<T>::~BinarySearchTree() {
  if( root_ ) {
    DeleteNode(root_);
  }
}

template <class T>
void BinarySearchTree<T>::DeleteNode(Node<T>* node) {
  if( node ) {
    DeleteNode( node->GetLeft() );
    DeleteNode( node->GetRight() );
    delete node; // Post Order Deletion
  }
}

template <class T>
bool BinarySearchTree<T>::Insert(const T& value) {
  Node<T>* new_node = new (std::nothrow) Node<T>(value);

  if( !new_node )
    return true; // Out of memory

  if( !root_ ) // Special case
    root_ = new_node;
  else
    InsertNode(root_, new_node);

  return false;
}

template <class T>
void BinarySearchTree<T>::InsertNode(Node<T>* root, Node<T>* ins) {
  if( ins->GetValue() <= root->GetValue() ) {
    if( root->GetLeft() ) // If there is a left child, keep searching
      InsertNode(root->GetLeft(), ins);
    else // Found the right spot
      root->SetLeft(ins);
  }
  else {
    if( root->GetRight() ) // If there is a right child, keep searching
      InsertNode(root->GetRight(), ins);
    else // Found the right spot
      root->SetRight(ins);
  }
}

template <class T>
void BinarySearchTree<T>::PrintPreOrder(Node<T>* root) const {
  if( root ) {
    root->Print();                   // Parent
    PrintPreOrder(root->GetLeft());  // Left
    PrintPreOrder(root->GetRight()); // Right
  }
}

template <class T>
void BinarySearchTree<T>::PrintInOrder(Node<T>* root) const {
  if( root ) {
    PrintInOrder(root->GetLeft());  // Left
    root->Print();                  // Parent
    PrintInOrder(root->GetRight()); // Right
  }
}
template <class T>
void BinarySearchTree<T>::PrintPostOrder(Node<T>* root) const {
  if( root ) {
    PrintPostOrder(root->GetLeft());  // Left
    PrintPostOrder(root->GetRight()); // Right
    root->Print();                    // Parent
  }
}

// Depth-First Search
template <class T>
Node<T>* BinarySearchTree<T>::Find(Node<T>* root, const T& value) const {
  if( root ) {
    //std::cout << root->GetValue() << std::endl;
    if( root->GetValue() == value )
      return root; // Found
    else if( value < root->GetValue() )
      return Find( root->GetLeft(), value );
    else
      return Find( root->GetRight(), value );
  }

  return NULL;
}

template <class T>
int BinarySearchTree<T>::Height(Node<T>* root) const {
  int height = 0;
  if( root ) {
    int left  = Height(root->GetLeft());
    int right = Height(root->GetRight());
    height = 1 + ((left > right) ? left : right) ;
  }
  return height;
}

template <class T>
void BinarySearchTree<T>::PrintBreadthSearchFirst() const {
  List< Node<T>* > node_list;

  node_list.PushFront(root_);
  while( node_list.Length() > 0 ) {
    Node<T>* n;
    node_list.PopFront(&n);
    n->Print();
    if( n->GetLeft() )  node_list.PushBack(n->GetLeft());
    if( n->GetRight() ) node_list.PushBack(n->GetRight());
  }
}

}

#endif // DANI_SIMPLE_TREE_H_