Unhandled exception at 0x742808F2: Microsoft C++ exception: std::out_of_range at memory location 0x0055E9E4

Question

making a BST for a class. I'm not the most competent person with coding but I'm hoping to improve.

I'm trying to make a function that reads my tree inorder but whenever I return anything in my function it gives me this error, I'm sure it's a problem with a pointer somewhere but I can't pinpoint it. Any help would be appreciated.

(I know there's a fair few problems with declaring nodes globally like that, but atm would like to ignore that due to constraints on the files I've been given)

#include "stdafx.h"
#include "bst.h"
#include <iostream>

// Creating nodes  
Node* tree;
Node* treeNew;

using namespace std;

// Creates an empty binary tree - 1
BinarySearchTree::BinarySearchTree()
{
    root = new Node;
    root->left = nullptr;
    root->right = nullptr;
}

// Creates a binary tree with an initial value to store - 2
BinarySearchTree::BinarySearchTree(std::string word)
{
    root = new Node;
    root->data = word;
    root->left = nullptr;
    root->right = nullptr;
}

// Creates a binary tree by copying an existing tree - 3
BinarySearchTree::BinarySearchTree(const BinarySearchTree &rhs)
{
    if (tree != nullptr) {

        Node *treeNew = new Node;
        treeNew->data = tree->data;

        Node *leftTreeNew = new Node;
        leftTreeNew = tree->left;

        Node *rightTreeNew = new Node;
        rightTreeNew = tree->right;
    }
    else {
        treeNew = NULL;
    }
}

// Helper function for destroying the tree
void destroyTreeHelper(Node* tree) {
    if (tree == nullptr) {
        return;
    }
    if (tree->left != nullptr) {
        destroyTreeHelper(tree->left);
    }
    if (tree->right != nullptr) {
        destroyTreeHelper(tree->right);
    }
    delete tree;
    return;
}

// Destroys (cleans up) the tree - 4
BinarySearchTree::~BinarySearchTree()
{
    if (tree == nullptr) {
        return;
    }
    if (root != nullptr) {
        destroyTreeHelper(root);
    }
}

// Helper function for insert
void insertHelper(Node* tree, std::string word) {
    Node *nextNode = tree;
    Node *currentNode;

    if (nextNode != nullptr) {
        currentNode = nextNode;

        if (word < currentNode->data) {
            nextNode = currentNode->left;
        }
        else {
            nextNode = currentNode->right;
        }
    }
}

// Adds a word to the tree
void BinarySearchTree::insert(std::string word)
{
    if (root != nullptr) {
        insertHelper(root, word);
    }
}

// Removes a word from the tree
void BinarySearchTree::remove(std::string word)
{

}

// Checks if a word is in the tree
bool BinarySearchTree::exists(std::string word) const
{
    Node* tree = root;
    while (tree != nullptr) {
        if (tree->data == word) {
            return true;
        }
        else {
            if (word > tree->data) {
                tree = tree->right;
            }
            else {
                tree = tree->left;
            }
        }
    }
    return false;
}

// Helper function for inorder
void inOrderHelper(Node* tree, std::string tempString) {
    if (tree == nullptr) {
        std::cout << "Tree is empty" << std::endl;
        return;
    }
    if (tree != nullptr) {
        inOrderHelper(tree->left, tempString);
        tempString = tree->data + std::string(" ");
        inOrderHelper(tree->right, tempString);
    }
}

// Prints the tree to standard out in numerical order
std::string BinarySearchTree::inorder() const
{
    std::string tempString = "";
    inOrderHelper(root, tempString);
    tempString.erase(tempString.size() - 1);
    return tempString;
}

The code produces

The tree is empty
The tree is empty

before crashing giving me the error in the debugger

Unhandled exception at 0x742808F2 in Coursework.exe: Microsoft C++ exception: std::out_of_range at memory location 0x0055E9E4.

Here's my given header file.

#pragma once

#include <iostream>
#include <string>

// Node of the tree
struct Node
{
    // Data stored in this node of the tree
    std::string data;
    // The left branch of the tree
    Node *left = nullptr;
    // The right branch of the tree
    Node *right = nullptr;
};

class BinarySearchTree
{
private:
    // Pointer to root of the tree
    Node *root = nullptr;
public:
    // Creates an empty binary tree
    BinarySearchTree();
    // Creates a binary tree with an inital word to store
    BinarySearchTree(std::string word);
    // Creates a binary tree by copying an existing tree
    BinarySearchTree(const BinarySearchTree &rhs);
    // Destroys (cleans up) the tree
    ~BinarySearchTree();
    // Adds a word to the tree
    void insert(std::string word);
    // Removes a word from the tree
    void remove(std::string word);
    // Checks if a word is in the tree
    bool exists(std::string word) const;
    // Creates a string representing the tree in alphabetical order
    std::string inorder() const;
    // Creates a string representing the tree in pre-order
    std::string preorder() const;
    // Creates a string representing the tree in post-order
    std::string postorder() const;
    // Checks if two trees are equal
    bool operator==(const BinarySearchTree &other) const;
    // Checks if two trees are not equal
    bool operator!=(const BinarySearchTree &other) const;
    // Reads in words from an input stream into the tree
    friend std::istream& operator>>(std::istream &in, BinarySearchTree &tree);
    // Writes the words, in-order, to an output stream
    friend std::ostream& operator<<(std::ostream &out, const BinarySearchTree &tree);
};

Here's my given test file to test my functions

#include <iostream>
#include <string>
#include "stdafx.h"
#include <sstream>
#include "bst.h"

using namespace std;

int main(int argc, char **argv)
{
    // Test 1 - basic constructor
    BinarySearchTree *tree = new BinarySearchTree();
    string str = tree->inorder();
    if (str != string(""))
        cerr << "ERROR - test 1 failed (basic constructor)" << endl;
    else
        cout << "Test 1 passed (basic constructor)" << endl;
    delete tree;

    // Test 2 - single value constructor
    tree = new BinarySearchTree("hello");
    str = tree->inorder();

    if (str != string("hello"))
        cerr << "ERROR - test 2 failed (single value constructor)" << endl;
    else
        cout << "Test 2 passed (single value constructor)" << endl;
    delete tree;

    tree = new BinarySearchTree();
    // Test 3 - insertion check
    tree->insert("fish");
    tree->insert("aardvark");
    tree->insert("zeebra");
    tree->insert("dog");
    tree->insert("cat");
    str = tree->inorder();

    if (str != string("aardvark cat dog fish zeebra"))
        cerr << "ERROR - test 3 failed (insertion check)" << endl;
    else
        cout << "Test 3 passed (insertion check)" << endl;

    // Test 4 - exists check

    if (tree->exists("zeebra") && tree->exists("cat") && !tree->exists("bird") && !tree->exists("snake"))
        cout << "Test 4 passed (exists check)" << endl;
    else
        cerr << "ERROR - test 4 failed (exists check)" << endl;


    // Test 5a - copy constructor part 1
    BinarySearchTree *tree2 = new BinarySearchTree(*tree);
    str = tree2->inorder();
    if (str != string("aardvark cat dog fish zeebra"))
        cerr << "ERROR - test 5a failed (copy constructor part 1)" << endl;
    else
        cout << "Test 5a passed (copy constructor part 1)" << endl;

    // Test 5b - copy constructor part 2
    tree2->insert("mouse");
    if (tree->inorder() == tree2->inorder())
        cerr << "ERROR - test 5b failed (copy constructor part 2 - deep copy check)" << endl;
    else
        cout << "Test 5b passed (copy constructor part 2 - deep copy check)" << endl;
    delete tree2;
    tree2 = nullptr;

    // Test 6 - preorder print
    str = tree->preorder();
    if (str != string("fish aardvark dog cat zeebra"))
        cerr << "ERROR - test 6 failed (pre-order print)" << endl;
    else
        cout << "Test 6 passed (pre-order print)" << endl;

    // Test 7- postorder print
    str = tree->postorder();
    if (str != string("cat dog aardvark zeebra fish"))
        cerr << "ERROR - test 7 failed (post-order print)" << endl;
    else
        cout << "Test 7 passed (post-order print)" << endl;
    delete tree;

    //
//    

    // Test 8 - remove check part 1
    tree = new BinarySearchTree();
    tree->insert("green");
    tree->insert("cyan");
    tree->insert("blue");
    tree->insert("red");
    tree->insert("orange");
    tree->insert("yellow");
    tree->remove("gold");
    str = tree->inorder();
    if (str != string("blue cyan green orange red yellow"))
        cerr << "ERROR - test 8 failed (remove check part 1 - value not in tree)" << endl;
    else
        cout << "Test 8 passed (remove check part 1 - value not in tree)" << endl;
    delete tree;

    // Test 9 - remove check part 2
    tree = new BinarySearchTree();
    tree->insert("green");
    tree->insert("cyan");
    tree->insert("blue");
    tree->insert("red");
    tree->insert("orange");
    tree->insert("yellow");
    tree->remove("blue");
    str = tree->inorder();
    if (str != string("cyan green orange red yellow"))
        cerr << "ERROR - test 9 failed (remove check part 2 - leaf value)" << endl;
    else
        cout << "Test 9 passed (remove check part 2 - leaf value)" << endl;
    delete tree;

    // Test 10 - remove check part 3
    tree = new BinarySearchTree();
    tree->insert("green");
    tree->insert("cyan");
    tree->insert("blue");
    tree->insert("red");
    tree->insert("orange");
    tree->insert("yellow");
    tree->remove("cyan");
    str = tree->inorder();
    if (str != string("blue green orange red yellow"))
        cerr << "ERROR - test 10 failed (remove check part 3 - node with one child)" << endl;
    else
        cout << "Test 10 passed (remove check part 3 - node with one child)" << endl;
    delete tree;

    // Test 11 - remove check part 4
    tree = new BinarySearchTree();
    tree->insert("green");
    tree->insert("cyan");
    tree->insert("blue");
    tree->insert("red");
    tree->insert("orange");
    tree->insert("yellow");
    tree->remove("red");
    str = tree->inorder();
    if (str != string("blue cyan green orange yellow"))
        cerr << "ERROR - test 11 failed (remove check part 4 - node with two children)" << endl;
    else
        cout << "Test 11 passed (remove check part 4 - node with two children)" << endl;
    delete tree;

    // Test 12 - output operator
    tree = new BinarySearchTree();
    tree->insert("hello");
    tree->insert("goodbye");
    tree->insert("bonjour");
    tree->insert("aurevoir");
    stringstream stream1;
    stream1 << *tree;
    if (stream1.str() != string("aurevoir bonjour goodbye hello"))
        cerr << "ERROR - test 12 failed (output operator)" << endl;
    else
        cout << "Test 12 passed (output operator)" << endl;
    delete tree;

    stringstream stream2;
    // Test 13 - input operator
    stream2 << "hello " << "world " << "welcome " << "abc " << endl;
    tree = new BinarySearchTree();
    stream2 >> *tree;
    if (tree->inorder() != string("abc hello welcome world"))
        cerr << "ERROR - test 13 failed (input operator)" << endl;
    else
        cout << "Test 13 passed (input operator)" << endl;
    delete tree;

    return 0;
}

I don't know why tree is empty either which is confusing me, any help would be appreciated

The problem lies with the last

return tempString;

in the first block of code

Thanks Ken for the help, problem was my tempString didn't contain anything, appended my code and it seems to be working

// Helper function for inorder
std::string inOrderHelper(Node* tree, std::string &tempString) {
    if (tree == nullptr) {
        return std::string("Tree is empty");
    }
    if (tree != nullptr) {
        inOrderHelper(tree->left, tempString);
        tempString = tree->data + std::string(" ");
        inOrderHelper(tree->right, tempString);
    }
    std::cout << tempString << std::endl;
    return tempString;
}

// Prints the tree to standard out in numerical order
std::string BinarySearchTree::inorder() const
{
    std::string tempString;
    inOrderHelper(root, tempString);
    if (tempString.size()) {
        tempString.erase(tempString.size() - 1);
    }
    return tempString;
}

Answer 1

In this function:

// Prints the tree to standard out in numerical order
std::string BinarySearchTree::inorder() const
{
    std::string tempString = "";
    inOrderHelper(root, tempString);
    tempString.erase(tempString.size() - 1);
    return tempString;
}

inOrderHelper() takes the string by value, so tempString stays empty, thus we get:

tempString.erase(0 - 1);

Trying to erase the -1th character of the string will fail with said std::out_of_range. The quickest fix is probably:

if (tempString.size())
    tempString.erase(tempString.size() - 1);

If the string size is not zero, erase the last character.

Also, you probably want:

// Helper function for inorder
void inOrderHelper(Node* tree, std::string &tempString) {

So that you can return the altered string.