title: Binary Search Tree Template
body: <p>I'm fairly new to c++ and I've recently received a project to create my own Binary Search Tree using a Template. The goal is for the Binary Tree to be able to take in any kind of data type. IntBinaryTree.h should be able to take in object of EmployeeInfo. I've gotten it to compile but I get an error message of <strong>glibc detected double free or corruption (fasttop)</strong> I'm not exactly sure what this means. Also I'm not sure if I've set the program up correctly. Also note, I'm testing functions 1 by 1 in main.cpp that's why there is only insert function being used.</p>
  
  <p><strong><em>Update</em></strong> I allocated memory for the insertNode function by TreeNode *newNode = new TreeNode, now I get error message of "in instantiation of void IntBinaryTree::insertNode(T) [with T = EmployeeInfo]:  main.cpp:22:29 required from here "</p>
  
  <pre><code>#ifndef EMPLOYEEINFO_H
  #define EMPLOYEEINFO_H
  
  #include&lt;iostream&gt;
  #include&lt;string&gt;
  #include&lt;cstdlib&gt;
  
  using namespace std;
  
  class EmployeeInfo
  {
  public:
      EmployeeInfo(int, string);
      ~EmployeeInfo();
      //void print();
      int getEmployeeID();
      string getEmployeeName();
      void setEmployeeID(int);
      void setEmployeeName(string);
      bool operator ==(const EmployeeInfo &amp;eO1) {return EmployeeID == eO1.EmployeeID;}
      bool operator &gt;(const EmployeeInfo &amp;eO1) {return EmployeeID &gt; eO1.EmployeeID;}
      bool operator &lt;(const EmployeeInfo &amp;eO1) {return EmployeeID &lt; eO1.EmployeeID;}
  
  private:    
      int EmployeeID;
      string EmployeeName;
  };
  
  #endif
  
  
  #include"EmployeeInfo.h"
  #include&lt;iostream&gt;
  #include&lt;string&gt;
  #include&lt;cstdlib&gt;
  
  using namespace std;
  
  EmployeeInfo::EmployeeInfo(int empID, string name)
  {
     EmployeeID = empID;
     EmployeeName = name;
  }
  
  EmployeeInfo::~EmployeeInfo()
  {
  }
  
  int EmployeeInfo::getEmployeeID()
  {
     return EmployeeID;
  }
  
  string EmployeeInfo::getEmployeeName()
  {
     return EmployeeName;
  }
  
  void EmployeeInfo::setEmployeeID(int empID)
  {
     EmployeeID = empID;
  }
  
  void EmployeeInfo::setEmployeeName(string name)
  {
     EmployeeName = name;
  }
  
  
  #ifndef INTBINARYTREE_H
  #define INTBINARYTREE_H
  
  #include &lt;iostream&gt;
  #include&lt;string&gt;
  #include&lt;cstdlib&gt;
  #include &lt;iomanip&gt;
  
  using namespace std;
  
  template&lt;class T&gt;
  struct TreeNode
  {
     T value;
     TreeNode&lt;T&gt; *left;
     TreeNode&lt;T&gt; *right;
  };
  
  template&lt;class T&gt;
  class IntBinaryTree
  {
     private:
        TreeNode&lt;T&gt;* root;
        void insert(TreeNode&lt;T&gt; *&amp;, TreeNode&lt;T&gt; *&amp;);
        void destroySubTree(TreeNode&lt;T&gt; *);
        void deleteNode(T, TreeNode&lt;T&gt; *&amp;);
        void makeDeletion(TreeNode&lt;T&gt; *&amp;);
        void displayInOrder(TreeNode&lt;T&gt; *) const;
        void displayPreOrder(TreeNode&lt;T&gt; *) const;
        void displayPostOrder(TreeNode&lt;T&gt; *) const;
     public:
        //Constructor
        IntBinaryTree();
       ~IntBinaryTree(){destroySubTree(root);}
  
        //Binary Tree Operations
        void insertNode(T);
        bool searchNode(T);
        void remove(T);
  
        void displayInOrder() const{ displayInOrder(root);}
        void displayPreOrder() const{ displayPreOrder(root);}
        void displayPostOrder() const{ displayPostOrder(root);}
  
  };
  
  template&lt;class T&gt;
  IntBinaryTree&lt;T&gt;::IntBinaryTree()
  {
     root = NULL;
  }
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::insert(TreeNode&lt;T&gt; *&amp;nodePtr, TreeNode&lt;T&gt; *&amp;newNode)
  {
     if (nodePtr == NULL)
         nodePtr = newNode;
     else if (newNode-&gt;value &lt; nodePtr-&gt;value)
         insert(nodePtr-&gt;left, newNode);
     else 
         insert(nodePtr-&gt;right, newNode);
  }
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::insertNode(T val)
  {
     TreeNode&lt;T&gt; *newNode;
  
     newNode-&gt;value = val;
     newNode-&gt;left = newNode-&gt;right = NULL;
  
     //Insert the Node
     insert(root, newNode);
  }
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::displayInOrder(TreeNode&lt;T&gt; *nodePtr) const
  {
     if(nodePtr){
         displayInOrder(nodePtr-&gt;left);
         cout &lt;&lt; nodePtr-&gt;value &lt;&lt; " ";
         displayInOrder(nodePtr-&gt;right);
      }
  } 
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::displayPreOrder(TreeNode&lt;T&gt; *nodePtr) const
  {
     if(nodePtr){
         cout &lt;&lt; nodePtr-&gt;value &lt;&lt; " ";
         displayPreOrder(nodePtr-&gt;left);
         displayPreOrder(nodePtr-&gt;right);
     }
  }
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::displayPostOrder(TreeNode&lt;T&gt; *nodePtr) const{
     if(nodePtr){
         displayPostOrder(nodePtr-&gt;left);
         displayPostOrder(nodePtr-&gt;right);
         cout &lt;&lt; nodePtr-&gt;value &lt;&lt; " ";
     }
  }
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::destroySubTree(TreeNode&lt;T&gt; *nodePtr){
     if(nodePtr != NULL)
     {
         if(nodePtr-&gt;left != NULL)
         {
              destroySubTree(nodePtr-&gt;left);
         }
         if(nodePtr-&gt;right != NULL)
         {
             destroySubTree(nodePtr-&gt;right);
         }
         delete nodePtr;
     }
  
     cout &lt;&lt; "Binary Tree Destroyed\n";
  }
  
  template&lt;class T&gt;
  bool IntBinaryTree&lt;T&gt;::searchNode(T val){
     TreeNode&lt;T&gt;* nodePtr = root;
  
     while(nodePtr){
         if (nodePtr-&gt;value == val)
             return true;
         else if (val &lt; nodePtr-&gt;value)
             nodePtr = nodePtr-&gt;left;
         else
             nodePtr = nodePtr-&gt;right;
     }
     return false;
  }
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::remove(T val){
     deleteNode(val, root);
  } 
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::deleteNode(T val, TreeNode&lt;T&gt; *&amp;nodePtr){
     if (val &lt; nodePtr-&gt;value)
         deleteNode(val, nodePtr-&gt;left);
     else if (val &gt; nodePtr-&gt;value)
         deleteNode(val, nodePtr-&gt;right);
     else
         makeDeletion(nodePtr);
  }
  
  template&lt;class T&gt;
  void IntBinaryTree&lt;T&gt;::makeDeletion(TreeNode&lt;T&gt; *&amp;nodePtr){
     TreeNode&lt;T&gt; *tempNodePtr;
  
     if (nodePtr == NULL)
         cout &lt;&lt; "Cannot delete empty node\n";
     else if(nodePtr-&gt;right == NULL)
     {
         tempNodePtr = nodePtr;
         nodePtr = nodePtr-&gt;left;
         delete tempNodePtr;
     }
     else if(nodePtr-&gt;left == NULL)
     {
         tempNodePtr = nodePtr;
         nodePtr = nodePtr-&gt;right;
         delete tempNodePtr;
     }
     //If the node has two Children
     else
     {
         //Move one node to the right
         tempNodePtr = nodePtr-&gt;right;
         //Go to the end left node
         while(tempNodePtr-&gt;left)
            tempNodePtr = tempNodePtr-&gt;left;
         //Reattach the left subtree
         tempNodePtr-&gt;left = nodePtr-&gt;left;
         tempNodePtr = nodePtr;
         //Reattach the right subtree
         nodePtr = nodePtr-&gt;right;
         delete tempNodePtr;
     }
  }
  
  #endif
  
  
  
  #include"EmployeeInfo.cpp"
  #include"IntBinaryTree.h"
  #include&lt;iostream&gt;
  #include&lt;string&gt;
  #include&lt;cstdlib&gt;
  
  using namespace std;
  
  int main()
  {       
     IntBinaryTree&lt;EmployeeInfo&gt; mytree;
  
     EmployeeInfo employee1(1021, "John Williams");
     EmployeeInfo employee2(1057, "Bill Witherspoon");
     EmployeeInfo employee3(2487, "Jennifer Twain");
     EmployeeInfo employee4(3769, "Sophia Lancaster");
     EmployeeInfo employee5(1017, "Debbie Reece");
     EmployeeInfo employee6(1275, "George McMullen");
     EmployeeInfo employee7(1899, "Ashley Smith");
     EmployeeInfo employee8(4218, "Josh Plemmons");
  
     mytree.insertNode(employee1);
     mytree.insertNode(employee2);
     mytree.insertNode(employee3);
     mytree.insertNode(employee4);
     mytree.insertNode(employee5);
     mytree.insertNode(employee6);
     mytree.insertNode(employee7);
     mytree.insertNode(employee8);
  
     return 0;
  } 
  </code></pre>