title: Binary Search Tree PostOrder and PreOrder Traversals are wrong
body: <p>I'm working on this homework where I need to print my binary search tree in preorder, postorder, and inorder. However, it seems like only my inorder method is working.  I have used the following test case to check my work.  </p>
  
  <pre><code>http://www.theteacher99.btinternet.co.uk/theteacher/newalevel/cp4_5_4.htm
  </code></pre>
  
  <p>Can you take a look at my code below and see what I'm doing wrong. Any help/orientation would be appreciated. You don't have to solve it for me, just let me know what i'm doing wrong.  Thanks.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;fstream&gt;
  #include &lt;cstddef&gt;
  #include &lt;string&gt;
  #include &lt;sstream&gt;
  #include &lt;string&gt;
  
  using namespace std;
  
  struct TreeNode
  {
      string item;
      TreeNode *left;
      TreeNode *right;
  };
  
  class BinarySortTree
  {
  public:
      BinarySortTree();
      void readFile(string fileName);
      void insert(string key);
      void preorder();
      void postorder();
      void inorder();
      void test();
  
  private:
      TreeNode *root;
      void insert(string key, TreeNode *node);
      void preorderTraverse(TreeNode *node);
      void postorderTraverse(TreeNode *node);
      void inorderTraverse(TreeNode *node);
  };
  
  
  //default constructor, create new binary tree
  BinarySortTree::BinarySortTree()
  {
      root = NULL;
  }
  
  //reads the file and puts items in the tree
  void BinarySortTree::readFile(string fileName)
  {
      ifstream inputStream(fileName.c_str());
  
      if(inputStream.is_open())
      {
          string line;
  
          while( getline(inputStream, line) )
          {
              insert(line);
          }
      }
  }
  
  void BinarySortTree::insert(string key)
  {
      if(root != NULL)
      {
          insert(key, root);
      }
      else
      {
          root = new TreeNode;
          root-&gt;item = key;
          root-&gt;left = NULL;
          root-&gt;right = NULL;
      }
  }
  
  void BinarySortTree::insert(string key, TreeNode *node)
  {
      bool done = false;
  
      while(!done)
      {
          if(key.compare(node-&gt;item) &lt; 0)
          {
              if(node-&gt;left != NULL)
              {
                  node = node-&gt;left;
              }
              else
              {
                  node-&gt;left = new TreeNode;
                  node-&gt;left-&gt;item = key;
                  node-&gt;left-&gt;left = NULL;
                  node-&gt;left-&gt;right = NULL;
                  done = true;
              }
          }
          else if(key.compare(node-&gt;item) &gt; 0)
          {
              if(node-&gt;right != NULL)
              {
                  node = node-&gt;right;
              }
              else
              {
                  node-&gt;right = new TreeNode;
                  node-&gt;right-&gt;item = key;
                  node-&gt;right-&gt;left = NULL;
                  node-&gt;right-&gt;right = NULL;
                  done = true;
              }
          }
          else if(key.compare(node-&gt;item) == 0)
          {
              done = true;
          }
      }
  }
  
  void BinarySortTree::preorder()
  {
      cout &lt;&lt; "PreOrder Traversal" &lt;&lt; endl;
      preorderTraverse(root);
      cout &lt;&lt; endl;
  
  }
  
  /*
     1. Start at the root node
     2. Traverse the left subtree
     3. Traverse the right subtree
  */
  void BinarySortTree::preorderTraverse(TreeNode *node)
  {
      if(node != NULL)
      {
          cout &lt;&lt; node-&gt;item &lt;&lt; " ";
          preorderTraverse(node-&gt;left);
          preorderTraverse(node-&gt;right);
      }
  
  }
  
  void BinarySortTree::postorder()
  {
      cout &lt;&lt; "PostOrder Traversal" &lt;&lt; endl;
      postorderTraverse(root);
      cout &lt;&lt; endl;
  }
  
  /*
     1. Traverse the left subtree
     2. Traverse the right subtree
     3. Visit the root node
  */
  void BinarySortTree::postorderTraverse(TreeNode *node)
  {
      if(node != NULL)
      {
          postorderTraverse(node-&gt;left);
          postorderTraverse(node-&gt;right);
          cout &lt;&lt; node-&gt;item &lt;&lt; " ";
      }
  }
  
  void BinarySortTree::inorder()
  {
      cout &lt;&lt; "InOrder Traversal" &lt;&lt; endl;
      inorderTraverse(root);
      cout &lt;&lt; endl;
  }
  
  /*
     1. Traverse the left subtree
     2. Visit the root node
     3. Traverse the right subtree
  */
  void BinarySortTree::inorderTraverse(TreeNode *node)
  {
      if(node!= NULL)
      {
          inorderTraverse(node-&gt;left);
          cout &lt;&lt; node-&gt;item &lt;&lt; " ";
          inorderTraverse(node-&gt;right);
      }
  }
  
  void BinarySortTree::test()
  {
      cout &lt;&lt; root-&gt;item &lt;&lt; endl;
  }
  
  
  int main()
  {
      string fileName = "a4.txt";
      BinarySortTree bst;
      bst.readFile(fileName);
      bst.test();
  
      bst.preorder();
      bst.postorder();
      bst.inorder();
  
      return 0;
  }
  </code></pre>