rendered paste body#include <functional>template< typename T, typename Compare=std::less<int> >class BinaryTree { private: struct BTNode { BTNode(const T &value) : value(value){} const T &value; BTNode *left, *right; }; BTNode *root; public: BinaryTree(){root=0;} ~BinaryTree(){}; void insert(const T&val) { BTNode *node = new BTNode(val); if (root) insert(node, root); else root = node; } void remove(const T&val) { BTNode * parent = 0, node = root, tmp; //Loops until node is null or val == node->value while (node && (Compare(val,node->value) || Compare(node->value,val))) { tmp = node; node = Compare(val, node->value) ? node->left : node->right; parent = tmp; } if (!node) return; tmp = remove(node); if (parent) { if (parent->left == node) parent->left = tmp; else parent->right = tmp; } else root = tmp; delete node; } private: /** * Inserts node into parents tree */ void insert(BTNode * node, BTNode * parent) { if ( Compare(node->value,parent->value) ) { //node < parent if ( parent->left ) insert(node, parent->left); else parent->left = node; } else { if ( parent->right ) insert(node, parent->right); else parent->right = node; } } /** * @return A pointer to the node to replace with */ BTNode *remove(BTNode * node) { if (node->left) { if (node->right) insert(node->right, node->left); return node->left; } else if (node->right) return node->right; return 0; }};