title: C++ : Binary Search Tree getHeight() access violation
body: <p>First, I have already read <a href="https://stackoverflow.com/questions/10355641/c-binary-search-tree-status-access-violation-error-with-adding-nodes">C++ Binary Search Tree status access violation error with adding nodes</a> and <a href="https://stackoverflow.com/questions/13412076/inserting-in-a-binary-search-tree-access-violation-error">Inserting in a binary search tree access violation error</a> but am still having trouble fully implementing my binary tree. I am currently getting a Access violation in my get height class, but can't figure out why.</p>
  
  <pre><code>template &lt;typename Item, typename Key&gt;
  std::size_t BinarySearchTree&lt;Item, Key&gt;::height(TreeNode* node) const{
      if (node == NULL)
          return 0;
      //Debug     
      if(node == NULL)
          std::cout&lt;&lt; "node = Null"&lt;&lt; endl;
      else
          std::cout&lt;&lt; "node != Null"&lt;&lt; endl;
  
      if(node-&gt;left == NULL)
          std::cout&lt;&lt; "left = Null"&lt;&lt; endl;
      else
          std::cout&lt;&lt; "left != Null"&lt;&lt; endl;
  
      if(node-&gt;right == NULL)
          std::cout&lt;&lt; "right = Null"&lt;&lt; endl;
      else
          std::cout&lt;&lt; "right != Null"&lt;&lt; endl;
  
  
      //This will go through the list adding 1 at each layer it passes through
      std::size_t left = height(node-&gt;left);
      std::size_t right = height(node-&gt;right);
      //This will return the branch with the greatest height
      return 1 + std::max(left, right);
  }
  </code></pre>
  
  <p>And this is how I add elements to the tree</p>
  
  <pre><code>template &lt;typename Item, typename Key&gt;
  void BinarySearchTree&lt;Item, Key&gt;::insert(const Item&amp; value){
      insert(root, value);//start at the root node
  }//end insert
  
  template &lt;typename Item, typename Key&gt;
  void BinarySearchTree&lt;Item, Key&gt;::insert(TreeNode* node, const Item&amp; value){
      //if item == tree-&gt;data then stop the method 
      if (node == NULL){
          //Populate the null leaf node
          TreeNode* target = new TreeNode(value);//create a new node for the inserted parameter
          target-&gt;data = value;//the data is stored in the target node
          //increment the size counter
          treeSize++;
      }else if (value &lt; node-&gt;data)
          //If the item is less than the current nodes data then insert again
          insert(node-&gt;left, value);
      else
          //If the item is greater than the current nodes data then insert again
          insert(node-&gt;right, value);     
  }
  </code></pre>
  
  <p>I have no idea how I could get an access violation since I check for null pointers before calling the left or the right node. Any insight would be greatly appreciated. </p>
  
  <p>EDIT: I should also note that the left and right leafs of a node are initialized to NULL.</p>
  
  <p>FULL CODE:</p>
  
  <pre><code>#pragma once
  #include &lt;cstdlib&gt;
  
  namespace MySpace{
  
  template &lt;typename Item, typename Key = Item&gt;
  class BinarySearchTree{
      // private node class (only visible inside the BinarySearchTree class)
      struct TreeNode {
          TreeNode(const Item&amp; data = Item()) :
              data(data), left(NULL), right(NULL) { }
          ~TreeNode(){
              delete left; delete right;
              left = NULL; right = NULL;
          }
          Item data;//This is the object
          TreeNode* left;   // left child
          TreeNode* right;  // right child
      };
  
  public:
      //==========================Constructor=============================
      // creates an empty tree
      BinarySearchTree(){root = NULL; treeSize = 0;}
      // Postcondition: A copy of the binary search tree
      BinarySearchTree(BinarySearchTree&lt;Item, Key&gt;&amp; source);
  
      //==========================Destructor================================      
      ~BinarySearchTree(){delete root; root = NULL;}//will delete all branches recursively
      //=========================Public Methods============================
      // Postcondition: the current tree has been replaced with a copy of
      // the source binary serch tree. The return value is the calling object
      BinarySearchTree&lt;Item, Key&gt;&amp; operator =(BinarySearchTree&lt;Item, Key&gt;&amp; source);
      // returns the number of nodes in the tree
      std::size_t size() const{return treeSize;}
      // returns the height of the tree
      std::size_t height() const;
      // returns the minimum value in the tree
      const Item&amp; min() const;
      // returns the maximum value in the tree
      const Item&amp; max() const;
      // inserts a copy of the given value into the tree, unless one already exists
      void insert(const Item&amp; value);
      // removes an entry with the given key, if present in the tree
      bool remove(const Key&amp; key);
      // returns a pointer to an entry with the given key (if it exists), or NULL
      Item* search(const Key&amp; key) const;
      // if an entry with the key exists, applies the function
      template &lt;typename Function&gt;
      bool apply(const Key&amp; key, Function f);
      // applies a function to each value in the tree, via preorder traversal
      template &lt;typename Function&gt;
      void preorder(Function f);
      // applies a function to each value in the tree, via inorder traversal
      template &lt;typename Function&gt;
      void inorder(Function f);
      // applies a function to each value in the tree, via postorder traversal
      template &lt;typename Function&gt;
      void postorder(Function f);
      //Copy the nodes of a BST
      TreeNode* copy(const TreeNode *node){           
          //If the passed node is Null then return null
          if (node == NULL)
              return NULL;
          Item nodeData = node-&gt;data;
          TreeNode* copyNode = new TreeNode(nodeData);//create a new node with the data from the last one 
          copyNode-&gt;data = node-&gt;data;
          copyNode-&gt;left = copy(node-&gt;left);
          copyNode-&gt;right = copy(node-&gt;right);
          return copyNode;
      }
  
      //=========================Accessor============================
      TreeNode* getRoot(){return root;}
  
  private:
      //This is the root node for the binary tree
      TreeNode* root;
      std::size_t treeSize;
  
      //Checks the size of the BST to see if it is empty or not
      bool isEmpty() const{return(treeSize == 0)?true:false;}
  
      //These methods are used for recursion
      Item* search(TreeNode* node, const Key&amp; key) const;
      void insert(TreeNode* node, const Item&amp; value);
      bool remove(TreeNode* node, const Key&amp; key);
      std::size_t height(TreeNode* node) const;
      const Item&amp; min(TreeNode* node) const;
      const Item&amp; max(TreeNode* node) const;
      template &lt;typename Function&gt;
      void preorder(TreeNode* node, Function f);
      template &lt;typename Function&gt;
      void inorder(TreeNode* node, Function f);
      template &lt;typename Function&gt;
      void postorder(TreeNode* node, Function f);
  
  };
  
  //------------------------This is where the methods will get implemented------------------------
  //Copy constructor
  template &lt;typename Item, typename Key&gt;
  BinarySearchTree&lt;Item, Key&gt;::BinarySearchTree(BinarySearchTree&lt;Item, Key&gt;&amp; source){
      treeSize = source.size();
      TreeNode* tempNode = source.getRoot();
      //copy(tempNode);
  }
  
  template &lt;typename Item, typename Key&gt;
  BinarySearchTree&lt;Item, Key&gt;&amp; BinarySearchTree&lt;Item, Key&gt;::operator =(BinarySearchTree&lt;Item, Key&gt;&amp; source){
      if(&amp;source == this)
          return *this;
      treeSize = source.size();
      TreeNode* tempNode = source.getRoot();
      //copy(tempNode);
      return *this;
  }
  
  template &lt;typename Item, typename Key&gt;
  std::size_t BinarySearchTree&lt;Item, Key&gt;::height() const{
      if(root == NULL)
          std::cout&lt;&lt; "AAAAAAHHHHHHH!"&lt;&lt; endl;
      else
          std::cout&lt;&lt; "okay!"&lt;&lt; endl;
      return height(root);//start at the root
  }
  
  template &lt;typename Item, typename Key&gt;
  std::size_t BinarySearchTree&lt;Item, Key&gt;::height(TreeNode* node) const{
      if (node == NULL)
          return 0;
      //Debug     
      if(node == NULL)
          std::cout&lt;&lt; "node = Null"&lt;&lt; endl;
      else
          std::cout&lt;&lt; "node != Null"&lt;&lt; endl;
  
      if(node-&gt;left == NULL)
          std::cout&lt;&lt; "left = Null"&lt;&lt; endl;
      else
          std::cout&lt;&lt; "left != Null"&lt;&lt; endl;
  
      if(node-&gt;right == NULL)
          std::cout&lt;&lt; "right = Null"&lt;&lt; endl;
      else
          std::cout&lt;&lt; "right != Null"&lt;&lt; endl;
  
  
      //This will go through the list adding 1 at each layer it passes through
      std::size_t left = height(node-&gt;left);
      std::size_t right = height(node-&gt;right);
      //This will return the branch with the greatest height
      return 1 + std::max(left, right);
  
  }
  
  template &lt;typename Item, typename Key&gt;
  const Item&amp; BinarySearchTree&lt;Item, Key&gt;::min() const{
      return min(root);//start at the root
  }
  
  template &lt;typename Item, typename Key&gt;
  const Item&amp; BinarySearchTree&lt;Item, Key&gt;::min(TreeNode* node) const{
      if(!isEmpty()){
          //goes recursively until the left most leaf is found
          if(node-&gt;left == NULL)
              return node-&gt;data;
          else
              min(node-&gt;left);
      }
  
      return Item();
  }
  
  template &lt;typename Item, typename Key&gt;
  const Item&amp; BinarySearchTree&lt;Item, Key&gt;::max() const{
      return max(root);//start at the root
  }
  
  template &lt;typename Item, typename Key&gt;
  const Item&amp; BinarySearchTree&lt;Item, Key&gt;::max(TreeNode* node) const{
      if(!isEmpty()){
          //goes recursively until the right most leaf is found
          if(node-&gt;right == NULL)
              return node-&gt;data;
          else
              max(node-&gt;right);
      }
      return Item();
  }
  
  template &lt;typename Item, typename Key&gt;
  void BinarySearchTree&lt;Item, Key&gt;::insert(const Item&amp; value){
     insert(root, value);//start at the root node
  }//end insert
  
  template &lt;typename Item, typename Key&gt;
  void BinarySearchTree&lt;Item, Key&gt;::insert(TreeNode* node, const Item&amp; value){
      //if item == tree-&gt;data then stop the method 
      if (node == NULL){
          //Populate the null leaf node
          TreeNode* target = new TreeNode(value);//create a new node for the inserted parameter
          target-&gt;data = value;//the data is stored in the target node
          node = target;
          //increment the size counter
          treeSize++;
      }else if (value &lt; node-&gt;data)
          //If the item is less than the current nodes data then insert again
          insert(node-&gt;left, value);
      else
          //If the item is greater than the current nodes data then insert again
          insert(node-&gt;right, value);     
  }
  
  template &lt;typename Item, typename Key&gt;
  bool BinarySearchTree&lt;Item, Key&gt;::remove(const Key&amp; key){
      return remove(root, key);//default is to return false
  }
  
  template &lt;typename Item, typename Key&gt;
  bool BinarySearchTree&lt;Item, Key&gt;::remove(TreeNode* node, const Key&amp; key){
      //If the tree is not empty
      if(!isEmpty()){
          if (key &lt; node-&gt;data)
              //If the key is less than the Item than go to the left branch
              remove(node-&gt;left, key);
          else if (key &gt; node-&gt;data)
              //If the key is less than the Item than go to the right branch
              remove(node-&gt;right, key);
          else{
              //If the key is equal to the Item then...
              //decrement size
              treeSize--;
  
              // There are several cases I have to deal with
              // 1) a leaf node - easy
              // 2) a node with 1 child - left or right
              // 3) a node with 2 children - left and right
  
              if(node-&gt;left == NULL &amp;&amp; node-&gt;right == NULL){
                  delete node;//If the node was a leaf then just delete it
                  node = NULL;
              }else if(node-&gt;left != NULL || node-&gt;right != NULL){
                  TreeNode* tempNode = node;
                  //If either branch is empty, then delete the node
                  delete node;
                  //now set the node to the non empty branch
                  node = (tempNode-&gt;left != NULL)?tempNode-&gt;left:tempNode-&gt;right;
              }else{
                  //if there are two branches then make the right branch the node
                  TreeNode* switchNode = node-&gt;right;
  
                  //gets the left most node on the right branch
                  while(switchNode-&gt;left != NULL){
                         switchNode = switchNode-&gt;left;
                  }
                  //This puts the data into the passed node, but does not delete it!
                  node-&gt;data = switchNode-&gt;data;
                  //I don't know how many children the switch node has(Either 0 or 1), so I have to run the 
                  //method again on the switch node to remove it properly
                  remove(switchNode, switchNode-&gt;data);
              }           
              return true;//return true since the item was deleted
          }//end if
      }//end if not empty
      return false;
  }
  
  template &lt;typename Item, typename Key&gt;
  Item* BinarySearchTree&lt;Item, Key&gt;::search(const Key&amp; key) const{
      return search(root, key);
  }
  
  template &lt;typename Item, typename Key&gt;
  Item* BinarySearchTree&lt;Item, Key&gt;::search(TreeNode* node, const Key&amp; key) const{
      if (node == NULL){
          //If there is no node at this location return null
          return NULL;
      }else if (key &lt; node-&gt;data)
          //If the key is less than the Item than go to the left branch
          search(node-&gt;left, key);
      else if (key &gt; node-&gt;data)
          //If the key is less than the Item than go to the right branch
          search(node-&gt;right, key);
      else
          //If the key is equal to the Item than return the item
          return &amp;node-&gt;data;
  }
  
  template &lt;typename Item, typename Key&gt;
  template &lt;typename Function&gt;
  bool BinarySearchTree&lt;Item, Key&gt;::apply(const Key&amp; key, Function f){
      Item* data = search(key);
      if(data != NULL){
          f(*data);//do the function on the selected item
          return true;
      }
      return false;
  }
  
  template &lt;typename Item, typename Key&gt;
  template &lt;typename Function&gt;
  void BinarySearchTree&lt;Item, Key&gt;::preorder(Function f){
      preorder(root, f);//start at the root
  }
  
  template &lt;typename Item, typename Key = Item&gt;
  template &lt;typename Function&gt;
  void BinarySearchTree&lt;Item, Key&gt;::preorder(TreeNode* node, Function f){
      //If the node is not null then do the method
      if(node != NULL){
          //Then apply the function to the data
          f(node-&gt;data);
          //Do the branches last
          if(node-&gt;left) preorder(node-&gt;left, f);
          if(node-&gt;right) preorder(node-&gt;right, f);
      }else
          return;
  }
  
  template &lt;typename Item, typename Key&gt;
  template &lt;typename Function&gt;
  void BinarySearchTree&lt;Item, Key&gt;::inorder(Function f){
      inorder(root, f);//start at the root
  }
  
  template &lt;typename Item, typename Key = Item&gt;
  template &lt;typename Function&gt;
  void BinarySearchTree&lt;Item, Key&gt;::inorder(TreeNode* node, Function f){
      //If the node is not null then do the method
      if(node != NULL){
          //Do the function in between the two branches
          if(node-&gt;left) inorder(node-&gt;left, f);
          //Then apply the function to the data
          f(node-&gt;data);
          if(node-&gt;right) inorder(node-&gt;right, f);
      }else
          return;
  }
  
  template &lt;typename Item, typename Key = Item&gt;
  template &lt;typename Function&gt;
  void BinarySearchTree&lt;Item, Key&gt;::postorder(Function f){
      postorder(root, f);//start at the root
  }
  
  template &lt;typename Item, typename Key = Item&gt;
  template &lt;typename Function&gt;
  void BinarySearchTree&lt;Item, Key&gt;::postorder(TreeNode* node, Function f){
      //If the node is not null then do the method
      if(node != NULL){
          //Do the function in between the two branches
          if(node-&gt;left) postorder(node-&gt;left, f);
          if(node-&gt;right) postorder(node-&gt;right, f);
          //Then apply the function to the data
          f(node-&gt;data);
      }else
          return;
  }
  
  }
  </code></pre>
  
  <p>This is where the main function is</p>
  
  <pre><code>#include "BinarySearchTree.h" 
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;cassert&gt;
  #include &lt;algorithm&gt;
  #include &lt;utility&gt;
  #include &lt;cmath&gt;
  #include &lt;sstream&gt;
  using namespace std;
  using namespace MySpace;
  using namespace rel_ops;
  
  
  
  #define TreeType BinarySearchTree
  
  #define BALANCED false
  
  // #define ITERATORS
  
  
  // returns the ideal height of a tree with n nodes
  size_t balanced_height(size_t n) { 
      return (n &lt; 2) ? n : 1 + (size_t) (log10((double) n) / log10(2.0));
  }
  
  
  // a simple compound data type
  struct Person {
      string name;
      int age;
  
      bool operator &lt;(const Person&amp; other) const { return (name &lt; other.name); }
      bool operator ==(const Person&amp; other) const { return (name == other.name); }
  
      operator string() const { return name; }
  };
  
  
  // operators for comparing a string to a Person (a Key to an Item)
  bool operator &lt;(const string&amp; L, const Person&amp; R) { return L &lt; R.name; }
  bool operator &gt;(const string&amp; L, const Person&amp; R) { return L &gt; R.name; }
  bool operator ==(const string&amp; L, const Person&amp; R) { return L == R.name; }
  bool operator !=(const string&amp; L, const Person&amp; R) { return L != R.name; }
  bool operator &lt;=(const string&amp; L, const Person&amp; R) { return L &lt;= R.name; }
  bool operator &gt;=(const string&amp; L, const Person&amp; R) { return L &gt;= R.name; }
  
  
  // output operator for Person class
  ostream&amp; operator &lt;&lt;(ostream&amp; out, const Person&amp; p) { return out &lt;&lt; p.name; }
  
  
  template &lt;typename Item, typename Key&gt;
  void test_tree(TreeType&lt;Item, Key&gt;, const vector&lt;Item&gt;&amp;);
  
  
  int main() {
      const size_t NUM_VALUES = 15;
  
      // create vectors containing the values to use
      vector&lt;int&gt; nums(NUM_VALUES);
      vector&lt;Person&gt; people(NUM_VALUES);
  
      // populate them with values
      for (size_t i = 0; i &lt; NUM_VALUES; i++) {
          nums[i] = people[i].age = i;
          people[i].name = char('A' + i);
      }
  
      // create the empty trees
      TreeType&lt;int&gt; t1;
      TreeType&lt;Person, string&gt; t2;
  
      // testing when the data type is also the key
      cout &lt;&lt; "Testing case when Item type is also the Key type... " &lt;&lt; endl;
      test_tree(t1, nums);
      cout &lt;&lt; "Passed!\n\n";
  
      // testing when the Item type has a different Key type
      cout &lt;&lt; "Testing case with different Item and Key types... " &lt;&lt; endl;
      test_tree(t2, people);
      cout &lt;&lt; "Passed!\n\n";
  
      // all tests passed
      cout &lt;&lt; "Nicely done!" &lt;&lt; endl;
      return EXIT_SUCCESS;
  }
  
  
  // simple stringstreams for testing purposes
  stringstream s1, s2;
  
  
  // outputs a value to the stringstream for testing
  template &lt;typename Item&gt;
  void output_value(Item&amp; data) {
      s1 &lt;&lt; data;
  }
  
  
  // inserts the contents of the vector in way that yields a balanced tree
  template &lt;typename Item, typename Key&gt;
  void balanced_insert(TreeType&lt;Item, Key&gt;&amp; tree, const vector&lt;Item&gt; values, int beg, int end) {
      if (beg &gt; end) return;
  
      size_t mid = ceil((beg + end) / 2.0);
      tree.insert(values[mid]);
  
      if (beg != end) {
          balanced_insert(tree, values, beg, mid - 1);
          balanced_insert(tree, values, mid + 1, end);
      }
  }
  
  
  // fills ss with data in preorder fashion
  template &lt;typename Item&gt;
  void vector_preorder(stringstream&amp; ss, const vector&lt;Item&gt; values, int beg, int end) {
      if (beg &gt; end) return;
  
      size_t mid = ceil((beg + end) / 2.0);
      ss &lt;&lt; values[mid];
  
      if (beg != end) {
          vector_preorder(ss, values, beg, mid - 1);
          vector_preorder(ss, values, mid + 1, end);
      }
  }
  
  
  // fills ss with data in inorder fashion
  template &lt;typename Item&gt;
  void vector_inorder(stringstream&amp; ss, const vector&lt;Item&gt; values, int beg, int end) {
      if (beg &gt; end) return;
  
      size_t mid = ceil((beg + end) / 2.0);
  
      if (beg != end) vector_inorder(ss, values, beg, mid - 1);
  
      ss &lt;&lt; values[mid];
  
      if (beg != end) vector_inorder(ss, values, mid + 1, end);
  }
  
  
  // fills ss with data in postorder fashion
  template &lt;typename Item&gt;
  void vector_postorder(stringstream&amp; ss, const vector&lt;Item&gt; values, int beg, int end) {
      if (beg &gt; end) return;
  
      size_t mid = ceil((beg + end) / 2.0);
  
      if (beg != end) {
          vector_postorder(ss, values, beg, mid - 1);
          vector_postorder(ss, values, mid + 1, end);
      }
  
      ss &lt;&lt; values[mid];
  }
  
  
  template &lt;typename Item, typename Key&gt;
  void test_tree(TreeType&lt;Item, Key&gt; tree, const vector&lt;Item&gt;&amp; values) {
      // tree should initially be empty
      assert(tree.size() == 0);
      assert(tree.height() == 0);
  
      std::cout&lt;&lt;"DIM TEST 1 COMPLETE!"&lt;&lt;endl;
  
      // insert a single value (becomes root of tree)
      tree.insert(values[0]);
  
      // ensure that the tree has a size and height of 1...
      assert(tree.size() == 1);
      assert(tree.height() == 1);
  
      std::cout&lt;&lt;"DIM TEST 2 COMPLETE!"&lt;&lt;endl;
  
      // ensure the value appears in the tree...
      assert(tree.search(values[0]));
  
      // and that your function correctly returns a pointer to the value
      assert(*tree.search(values[0]) == values[0]);
  
      std::cout&lt;&lt;"SEARCH 1 COMPLETE!"&lt;&lt;endl;
  
      // testing removing the root node (resulting in an empty tree)
      assert(tree.remove(values[0]));
  
      std::cout&lt;&lt;"REMOVE 1 COMPLETE!"&lt;&lt;endl;
  
      // ensure that the tree is once again empty...
      assert(tree.size() == 0);
      assert(tree.height() == 0);
  
      std::cout&lt;&lt;"DIM TEST 3 COMPLETE!"&lt;&lt;endl;
  
      // ensure that removing a non-existent value doesn't fail (should return false)
      assert(!tree.remove(values[0]));
  
      std::cout&lt;&lt;"REMOVE 2 COMPLETE!"&lt;&lt;endl;
  
      // ensure that the value no longer appears in the tree...
      assert(!tree.search(values[0]));
  
      std::cout&lt;&lt;"SEARCH 2 COMPLETE!"&lt;&lt;endl;
  
      // insert all the values this time in sorted order...
      for (size_t i = 0; i &lt; values.size(); i++) {
          tree.insert(values[i]);
  
          // ensure the value appears in the tree...
          assert(tree.search(values[i]));
  
          // ensure that the size is correct...
          assert(tree.size() == i + 1);
  
          // height of tree depends on whether you're balancing as you go or not
          assert(tree.height() == (BALANCED ? balanced_height(tree.size()) : tree.size()));
      }
  
      std::cout&lt;&lt;"INSERT 1 COMPLETE!"&lt;&lt;endl;
  
      // ensure min and max work
      assert(tree.min() == *min_element(values.begin(), values.end()));
      assert(tree.max() == *max_element(values.begin(), values.end()));
  
      // remove all the values, starting with the root
      for (size_t i = 0; i &lt; values.size(); i++) {
          // remove the value
          tree.remove(values[i]);
  
          // ensure the value no longer appears in the tree...
          assert(!tree.search(values[i]));
  
          // ensure that the size is correct...
          assert(tree.size() == values.size() - i - 1);
  
          // height of tree depends on whether you're balancing as you go or not
          assert(tree.height() == (BALANCED ? balanced_height(tree.size()) : tree.size()));
      }
  
      std::cout&lt;&lt;"REMOVE 3 COMPLETE!"&lt;&lt;endl;
  
      // insert all the values this time in balanced order...
      balanced_insert(tree, values, 0, values.size() - 1);
  
      std::cout&lt;&lt;"INSERT 2 COMPLETE!"&lt;&lt;endl;
  
      // make sure the size is still right...
      assert(tree.size() == values.size());
  
      // height of tree should be ceil(log2(n))
      assert(tree.height() == balanced_height(tree.size()));
  
      std::cout&lt;&lt;"DIM TEST 4 COMPLETE!"&lt;&lt;endl;
  
      // can't insert duplicate values (size &amp; height shouldn't increase)
      // operation should simply fail silently (do nothing)
      tree.insert(values[0]);
      assert(tree.size() == values.size());
      assert(tree.height() == balanced_height(values.size()));
  
      // ensure min and max (still) work
      assert(tree.min() == *min_element(values.begin(), values.end()));
      assert(tree.max() == *max_element(values.begin(), values.end()));
  
      std::cout&lt;&lt;"MIN MAX 1 COMPLETE!"&lt;&lt;endl;
  
      // testing copy constructor
      TreeType&lt;Item, Key&gt;* copy = new TreeType&lt;Item, Key&gt;(tree);
      assert(copy-&gt;size() == tree.size());
      assert(copy-&gt;height() == tree.height());
  
      std::cout&lt;&lt;"DIM TEST 5 COMPLETE!"&lt;&lt;endl;
  
      // original should remain unchanged after copy modification
      copy-&gt;remove(values[1]);
      copy-&gt;remove(values[values.size() - 2]);
      assert(copy-&gt;size() == tree.size() - 2);
      assert(tree.search(values[1]));
      assert(tree.search(values[values.size() - 2]));
  
      std::cout&lt;&lt;"REMOVE 4 COMPLETE!"&lt;&lt;endl;
  
      // testing destructor
      delete copy;
  
      // the original should remain unchanged
      for (size_t i = 0; i &lt; values.size(); i++) {
          assert(tree.search(values[i]));
      }
  
      // testing assignment operator
      copy = new TreeType&lt;Item, Key&gt;;
      *copy = tree;
  
      // original should remain unchanged after copy modification
      copy-&gt;remove(values[1]);
      copy-&gt;remove(values[values.size() - 2]);
      assert(copy-&gt;size() == tree.size() - 2);
      assert(tree.search(values[1]));
      assert(tree.search(values[values.size() - 2]));
  
      // testing destructor
      delete copy;
  
      // the original should remain unchanged
      for (size_t i = 0; i &lt; values.size(); i++) {
          assert(tree.search(values[i]));
      }
  
      // testing preorder traversal
      s1.str(""); s2.str("");
      vector_preorder(s2, values, 0, values.size() - 1);
      tree.preorder(output_value&lt;Item&gt;);
      assert(s1.str() == s2.str());
  
      // testing inorder traversal
      s1.str(""); s2.str("");
      vector_inorder(s2, values, 0, values.size() - 1);
      tree.inorder(output_value&lt;Item&gt;);
      assert(s1.str() == s2.str());
  
      // testing postorder traversal
      s1.str(""); s2.str("");
      vector_postorder(s2, values, 0, values.size() - 1);
      tree.postorder(output_value&lt;Item&gt;);
      assert(s1.str() == s2.str());
  
      // testing apply
      s1.str(""); s2.str("");
      s2 &lt;&lt; values[0];
      tree.apply(values[0], output_value&lt;Item&gt;);
      assert(s1.str() == s2.str());
  
  #ifdef ITERATORS
      // testing iterators (smallest-to-largest order)
      typename TreeType&lt;Item, Key&gt;::iterator t = tree.begin();
      typename vector&lt;Item&gt;::const_iterator v = values.begin();
  
      while (t != tree.end()) {
          assert(*t == *v);
          ++t;
          ++v;
      }
  
      assert(v == values.end());
  #endif
  }
  </code></pre>