Binary Search Tree PostOrder and PreOrder Traversals are wrong

Question

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.

http://www.theteacher99.btinternet.co.uk/theteacher/newalevel/cp4_5_4.htm

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.

#include <iostream>
#include <fstream>
#include <cstddef>
#include <string>
#include <sstream>
#include <string>

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->item = key;
        root->left = NULL;
        root->right = NULL;
    }
}

void BinarySortTree::insert(string key, TreeNode *node)
{
    bool done = false;

    while(!done)
    {
        if(key.compare(node->item) < 0)
        {
            if(node->left != NULL)
            {
                node = node->left;
            }
            else
            {
                node->left = new TreeNode;
                node->left->item = key;
                node->left->left = NULL;
                node->left->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) > 0)
        {
            if(node->right != NULL)
            {
                node = node->right;
            }
            else
            {
                node->right = new TreeNode;
                node->right->item = key;
                node->right->left = NULL;
                node->right->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) == 0)
        {
            done = true;
        }
    }
}

void BinarySortTree::preorder()
{
    cout << "PreOrder Traversal" << endl;
    preorderTraverse(root);
    cout << 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 << node->item << " ";
        preorderTraverse(node->left);
        preorderTraverse(node->right);
    }

}

void BinarySortTree::postorder()
{
    cout << "PostOrder Traversal" << endl;
    postorderTraverse(root);
    cout << 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->left);
        postorderTraverse(node->right);
        cout << node->item << " ";
    }
}

void BinarySortTree::inorder()
{
    cout << "InOrder Traversal" << endl;
    inorderTraverse(root);
    cout << 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->left);
        cout << node->item << " ";
        inorderTraverse(node->right);
    }
}

void BinarySortTree::test()
{
    cout << root->item << endl;
}


int main()
{
    string fileName = "a4.txt";
    BinarySortTree bst;
    bst.readFile(fileName);
    bst.test();

    bst.preorder();
    bst.postorder();
    bst.inorder();

    return 0;
}

The code you have here seems correct. Can you elaborate on why you think it isn't working correctly? — templatetypedef
The code compiles fine without errors. The problem is that when I print the nodes, I DON'T get the same values as the test page that I'm using. I don't know maybe I'm just not printing in the correct order. — user445338
Adding my entire code... maybe my insertion method is incorrect because my root is 'A' — user445338
I'm looking and my insert method never inserts to the left. that is my problem — user445338
Questions on SO are supposed to act as a sort of canonical documentation, like a wiki page, so that they can help people in the future. Can you please roll back your edit, and put the code back in the question? As asked, the question is worthless without the code. — Merlyn Morgan-Graham

Merlyn Morgan-Graham Merlyn Morgan-Graham · Accepted Answer · 2011-03-13T06:41:41

You are doing nothing wrong. I got it compiling, and it works fine, and passes those tests. I didn't have to make a single change to the code you provided - just add to it so it compiled and initialized the structures correctly.

Make sure you assign your left/right pointers to NULL in your constructor for TreeNode, and properly pass in the D node as root. Also remember to delete any nodes you create via new TreeNode. If you create them on the stack (normal local variable without new), you of course don't have to delete them.

Binary Search Tree PostOrder and PreOrder Traversals are wrong

2 Answers