title: Binary Search Tree Implementation
body: <p>I've searched the forum, and tried to implement the code in the threads I found. But I've been working on this real simple program since about 10am, and can't solve the seg. faults for the life of me.</p>
  
  <p>Any ideas on what I'm doing wrong would be greatly appreciated. </p>
  
  <p>BST.h (All the implementation problems should be in here, and this has been updated some to reflect further development work, look at the history to see old versions.)</p>
  
  <pre><code>#ifndef BST_H_
  #define BST_H_
  
  #include &lt;stdexcept&gt;
  #include &lt;iostream&gt;
  #include "btnode.h"
  
  using namespace std;
  
  /*
      A class to represent a templated binary search tree.
  */
  template &lt;typename T&gt;
  class BST
  {
      private:
  
          //pointer to the root node in the tree
          BTNode&lt;T&gt;* root;
  
      public:
  
          //default constructor to make an empty tree
          BST();
  
          /*
              You have to document these 4 functions
          */
          void insert(T value);
          bool search(const T&amp; value) const;
          bool search(BTNode&lt;T&gt;* node, const T&amp; value) const;
          void printInOrder() const;
          void remove(const T&amp; value);
  
          //function to print out a visual representation
          //of the tree (not just print the tree's values 
          //on a single line)
          void print() const;
  
      private:
  
          //recursive helper function for "print()"
          void print(BTNode&lt;T&gt;* node,int depth) const;
  };
  
  /*
      Default constructor to make an empty tree
  */
  template &lt;typename T&gt;
  BST&lt;T&gt;::BST()
  {
      root = NULL;
  }
  
  template &lt;typename T&gt;
  void BST&lt;T&gt;::insert(T value)
  {
      BTNode&lt;T&gt;* newNode = new BTNode&lt;T&gt;(value);
      cout &lt;&lt; newNode-&gt;data;
      if(root == NULL)
      {
          root = newNode;
          return;
      }
      BTNode&lt;T&gt;* current = root;
      while(true)
      {
          if(current-&gt;left == NULL &amp;&amp; current-&gt;right == NULL)
              break;
          if(current-&gt;right != NULL &amp;&amp; current-&gt;left != NULL)
          {
              if(newNode-&gt;data &gt; current-&gt;data) 
                  current = current-&gt;right;
              else if(newNode-&gt;data &lt; current-&gt;data)
                  current = current-&gt;left;
          }
          else if(current-&gt;right != NULL &amp;&amp; current-&gt;left == NULL)
          {
              if(newNode-&gt;data &lt; current-&gt;data) 
                  break;
              else if(newNode-&gt;data &gt; current-&gt;data)
                  current = current-&gt;right;
          }
          else if(current-&gt;right == NULL &amp;&amp; current-&gt;left != NULL)
          {
              if(newNode-&gt;data &gt; current-&gt;data) 
                  break;
              else if(newNode-&gt;data &lt; current-&gt;data)
                  current = current-&gt;left;
          }
      }
  
      if(current-&gt;data &gt; newNode-&gt;data)
      {   
          current-&gt;left = newNode;
      /*  cout &lt;&lt; current-&gt;data &lt;&lt; "DATA" &lt;&lt; endl;
          cout &lt;&lt; &amp;current &lt;&lt; "ADDY" &lt;&lt; endl;
          cout &lt;&lt; &amp;current-&gt;left &lt;&lt; "L ADDY" &lt;&lt; endl;
          cout &lt;&lt; &amp;current-&gt;right &lt;&lt; "R ADDY" &lt;&lt; endl;*/
      }
      else
      {
          current-&gt;right = newNode;
          /*cout &lt;&lt; current-&gt;data &lt;&lt; "DATA" &lt;&lt; endl;
          cout &lt;&lt; &amp;current &lt;&lt; "ADDY" &lt;&lt; endl;
          cout &lt;&lt; &amp;current-&gt;left &lt;&lt; "L ADDY" &lt;&lt; endl;
          cout &lt;&lt; &amp;current-&gt;right &lt;&lt; "R ADDY" &lt;&lt; endl;*/
      }
      return;
  }
  
  //public helper function
  template &lt;typename T&gt;
  bool BST&lt;T&gt;::search(const T&amp; value) const
  {
      return(search(root,value)); //start at the root
  }
  
  //recursive function
  template &lt;typename T&gt;
  bool BST&lt;T&gt;::search(BTNode&lt;T&gt;* node, const T&amp; value) const 
  {
      if(node == NULL || node-&gt;data == value)
          return(node != NULL); //found or couldn't find value
      else if(value &lt; node-&gt;data)
          return search(node-&gt;left,value); //search left subtree
      else
          return search(node-&gt;right,value); //search right subtree
  }
  
  template &lt;typename T&gt;
  void BST&lt;T&gt;::printInOrder() const
  {
      //print out the value's in the tree in order
      //
      //You may need to use this function as a helper
      //and create a second recursive function
      //(see "print()" for an example)
  }
  
  template &lt;typename T&gt;
  void BST&lt;T&gt;::remove(const T&amp; value)
  {
      if(root == NULL)
      {
          cout &lt;&lt; "Tree is empty. No removal. "&lt;&lt;endl;
          return;
      }
      if(!search(value))
      {
          cout &lt;&lt; "Value is not in the tree. No removal." &lt;&lt; endl;
          return;
      }
      BTNode&lt;T&gt;* current = root;
      BTNode&lt;T&gt;* parent;
  
      cout &lt;&lt; root-&gt;data &lt;&lt; " ROOT" &lt;&lt; endl;
      cout &lt;&lt; current-&gt;data &lt;&lt; "CURRENT BEFORE" &lt;&lt; endl;
  
      while(current != NULL)
      {
          if(root-&gt;data == value)
          {
              delete current;
              return;
          }
          else if(value &gt; current-&gt;data)
          {
              parent = current; 
              current = current-&gt;right;
          }
          else
          {
              parent = current; 
              current = current-&gt;left;            
          }
      }
      cout &lt;&lt; current-&gt;data &lt;&lt; "CURRENT AFTER" &lt;&lt; endl;
  
    // 3 cases :
      //We're looking at a leaf node
  
      if(current-&gt;left == NULL &amp;&amp; current-&gt;right == NULL)             // It's a leaf
      {
          if(parent == current)
              delete parent;
          else if(parent-&gt;left == current)
          {
              parent-&gt;left = NULL;
              delete current;
          }
          else 
          {
              parent-&gt;right = NULL;
              delete current;
          }
          cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
          return;
      }
  
      // Node with single child
      if((current-&gt;left == NULL &amp;&amp; current-&gt;right != NULL) || (current-&gt;left != NULL &amp;&amp; current-&gt;right == NULL))
      {
          if(current-&gt;left == NULL &amp;&amp; current-&gt;right != NULL)
          {
              if(parent-&gt;left == current)
              {
                  parent-&gt;left = current-&gt;right;
                  cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
                  delete current;
              }
              else
              {
                  parent-&gt;right = current-&gt;right;
                  cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
                  delete current;
              }
          }
          else // left child present, no right child
          {
              if(parent-&gt;left == current)
              {
                  parent-&gt;left = current-&gt;left;
                  cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
                  delete current;
              }
              else
              {
                  parent-&gt;right = current-&gt;left;
                  cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
                  delete current;
              }
          }
          return;
      }
  
      //Node with 2 children - Replace node with smallest value in right subtree.
      if (current-&gt;left != NULL &amp;&amp; current-&gt;right != NULL)
      {
          BTNode&lt;T&gt;* check;
          check = current-&gt;right;
          if((check-&gt;left == NULL) &amp;&amp; (check-&gt;right == NULL))
          {
              current = check;
              delete check;
              current-&gt;right = NULL;
              cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
          }
          else // right child has children
          {
              //if the node's right child has a left child; Move all the way down left to locate smallest element
              if((current-&gt;right)-&gt;left != NULL)
              {
                  BTNode&lt;T&gt;* leftCurrent;
                  BTNode&lt;T&gt;* leftParent;
                  leftParent = current-&gt;right;
                  leftCurrent = (current-&gt;right)-&gt;left;
                  while(leftCurrent-&gt;left != NULL)
                  {
                      leftParent = leftCurrent;
                      leftCurrent = leftCurrent-&gt;left;
                  }
                  current-&gt;data = leftCurrent-&gt;data;
                  delete leftCurrent;
                  leftParent-&gt;left = NULL;
                  cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
              }
              else
              {
                  BTNode&lt;T&gt;* temp;
                  temp = current-&gt;right;
                  current-&gt;data = temp-&gt;data;
                  current-&gt;right = temp-&gt;right;
                  delete temp;
                  cout &lt;&lt; "The value " &lt;&lt; value &lt;&lt; " was removed." &lt;&lt; endl;
              }
          }
          return;
      }
  }
  
  /*
      Print out the values in the tree and their
      relationships visually.  Sample output:
  
                          22
                  18
          15
  10
                  9
          5
                  3
                          1
  */
  template &lt;typename T&gt;
  void BST&lt;T&gt;::print() const
  {
      print(root,0);
  }
  
  template &lt;typename T&gt;
  void BST&lt;T&gt;::print(BTNode&lt;T&gt;* node,int depth) const
  {
      if(node == NULL)
      {
          std::cout &lt;&lt; std::endl;
          return;
      }
  
      print(node-&gt;right,depth+1);
      for(int i=0; i &lt; depth; i++)
      {
          std::cout &lt;&lt; "\t";
      }
      std::cout &lt;&lt; node-&gt;data &lt;&lt; std::endl;
      print(node-&gt;left,depth+1);
  }
  
  #endif
  </code></pre>
  
  <p>main.cpp </p>
  
  <pre><code>#include "bst.h"    
  #include &lt;iostream&gt;
  using namespace std;
  
  int main()
  {
      BST&lt;int&gt; tree;
      cout &lt;&lt; endl &lt;&lt; "LAB #13 - BINARY SEARCH TREE PROGRAM" &lt;&lt; endl;
      cout &lt;&lt; "----------------------------------------------------------" &lt;&lt; endl;
      // Insert.
      cout &lt;&lt; endl &lt;&lt; "INSERT TESTS" &lt;&lt; endl;         // No duplicates allowed.
      tree.insert(0);
      tree.insert(5);
      tree.insert(15);
      tree.insert(25);
      tree.insert(20);
  
      // Search.
      cout &lt;&lt; endl &lt;&lt; "SEARCH TESTS" &lt;&lt; endl;
      int x = 0;
      int y = 1;
      if(tree.search(x))
          cout &lt;&lt; "The value " &lt;&lt; x &lt;&lt; " is on the tree." &lt;&lt; endl;
      else 
          cout &lt;&lt; "The value " &lt;&lt; x &lt;&lt; " is NOT on the tree." &lt;&lt; endl;
      if(tree.search(y))
          cout &lt;&lt; "The value " &lt;&lt; y &lt;&lt; " is on the tree." &lt;&lt; endl;
      else
          cout &lt;&lt; "The value " &lt;&lt; y &lt;&lt; " is NOT on the tree." &lt;&lt; endl;
  
      // Removal.
      cout &lt;&lt; endl &lt;&lt; "REMOVAL TESTS" &lt;&lt; endl;
      tree.remove(0);
      tree.remove(1);
      tree.remove(20);
  
      // Print.
      cout &lt;&lt; endl &lt;&lt; "PRINTED DIAGRAM OF BINARY SEARCH TREE" &lt;&lt; endl;
      cout &lt;&lt; "----------------------------------------------------------" &lt;&lt; endl;
      tree.print();
      cout &lt;&lt; endl &lt;&lt; "Program terminated. Goodbye." &lt;&lt; endl &lt;&lt; endl;
  }
  </code></pre>
  
  <p>BTNode.h</p>
  
  <pre><code>#ifndef BTNODE_H_
  #define BTNODE_H_
  
  #include &lt;iostream&gt;
  
  /*
      A class to represent a node in a
      binary search tree.
  */
  template &lt;typename T&gt;
  
      class BTNode
      {
          public:
  
              //constructor
              BTNode(T d);
  
              //the node's data value
              T data;
  
              //pointer to the node's left child
              BTNode&lt;T&gt;* left;
  
              //pointer to the node's right child
              BTNode&lt;T&gt;* right;
      };
  
      /*
          Simple constructor.  Sets the data
          value of the BTNode to "d" and defaults its
          left and right child pointers to NULL.
      */
      template &lt;typename T&gt;
      BTNode&lt;T&gt;::BTNode(T d)
      : left(NULL), right(NULL)
      {
          data = d;
      }
  
      #endif
  </code></pre>
  
  <p>Thanks.</p>