I am working on a school project for which I need to load a number of items parsed from a CSV file to a binary search tree object. When I use a CSV file containing about 180 items it works fine, but when I use a CSV file containing just under 18,000 I receive a stack overflow error. I was wondering if anyone can assist. Here is the code (a lot of which was provided to me)...
#include <iostream>
#include <time.h>
#include "CSVparser.hpp"
using namespace std;
double strToDouble(string str, char ch);
// define a structure to hold bid information
struct Bid {
string bidId; // unique identifier
string title;
string fund;
double amount;
Bid() {
amount = 0.0;
}
};
// FIXED (1): Internal structure for tree node
struct Node {
Bid bid;
Node* left;
Node* right;
//default constructor
Node() {
left = nullptr;
right = nullptr;
}
//constructor which receives bid parameter
Node(Bid curBid) : Node() {
this->bid = curBid;
}
};
class BinarySearchTree {
private:
Node* root;
void addNode(Node* node, Bid bid);
void inOrder(Node* node);
Node* removeNode(Node* node, string bidId);
public:
BinarySearchTree();
virtual ~BinarySearchTree();
void InOrder();
void Insert(Bid bid);
void Remove(string bidId);
Bid Search(string bidId);
};
//constructor
BinarySearchTree::BinarySearchTree() {
// initialize housekeeping variables
root = nullptr;
}
//destructor
BinarySearchTree::~BinarySearchTree() {
// recurse from root deleting every node
}
//Traverse the tree in order
void BinarySearchTree::InOrder() {
this->inOrder(root);
}
//Insert a bid
void BinarySearchTree::Insert(Bid bid) {
// FIXED (2a) Implement inserting a bid into the tree
//if root is null then it gets set to new bid pointer
if (root == nullptr) {
root = new Node(bid);
}
else { //if root isn't null then adds the bid to the tree
this->addNode(root, bid);
}
}
//Remove a bid
void BinarySearchTree::Remove(string bidId) {
// FIXED (4a) Implement removing a bid from the tree
//removes requested node
this->removeNode(root, bidId);
}
//Search for a bid
Bid BinarySearchTree::Search(string bidId) {
// FIXED (3) Implement searching the tree for a bid
//initialize to root because that is where the search begins
Node* current = root;
//search through tree until bottom or until bid is found
while (current != nullptr) {
//if current bid matches search, returns it
if (bidId.compare(current->bid.bidId) == 0) {
return current->bid;
}
//bid parameter is less than current bid, continues searching to the left
if (bidId.compare(current->bid.bidId) < 0) {
current = current->left;
}
else { //bid parameter is greater than current bid, continues searching to the right
current = current->right;
}
}
//if while loop is exited without finding a match, an empty bid is created and returned
Bid bid;
return bid;
}
/**
* Add a bid to some node (recursive)
*
* @param node Current node in tree
* @param bid Bid to be added
*/
void BinarySearchTree::addNode(Node* node, Bid bid) {
// FIXED (2b) Implement inserting a bid into the tree
//if the bid parameter is less than the current node, then add to the left
if (bid.bidId.compare(node->bid.bidId) < 0) {
if (node->left == nullptr) { //if left node is null then it adds the new node here
node->left = new Node(bid);
}
else {
this->addNode(node->left, bid); //recursively calls addnode until bottom is reached
}
}
else { //add to right
if (node->right == nullptr) { //if left node is null then it adds the new node here
node->right = new Node(bid);
}
else {
this->addNode(node->right, bid); //recursively calls addnode until bottom is reached
}
}
}
void BinarySearchTree::inOrder(Node* node) {
if (node != nullptr) {
inOrder(node->left);
cout << node->bid.bidId
<< ": "
<< node->bid.title
<< " | "
<< node->bid.amount
<< " | "
<< node->bid.fund
<< endl;
inOrder(node->right);
}
}
Node* BinarySearchTree::removeNode(Node* node, string bidId) {
//if this node is null then return
if (node == nullptr) {
return node;
}
//if bid parameter is less than current node, searches left recursively
if (bidId.compare(node->bid.bidId) < 0) {
node->left = removeNode(node->left, bidId);
}
else if (bidId.compare(node->bid.bidId) > 0) { //if bid parameter is greater than current node, searches right recursively
node->right = removeNode(node->right, bidId);
}
else { //if its not < or > then its ==, so it needs to be removed since it matches the parameter bidId
//no children so node can just be removed
if ((node->left == nullptr) && (node->right == nullptr)) {
delete node;
node = nullptr;
}
//if one child to left
if ((node->left != nullptr) && (node->right == nullptr)) {
Node* temp = node;
node = node->left;
delete temp;
} //if one child to right
else if ((node->left == nullptr) && (node->right != nullptr)) {
Node* temp = node;
node = node->left;
delete temp;
} //if two children
else {
Node* temp = node;
node = node->right;
while (temp->left != nullptr) {
temp = temp->left;
}
node->bid = temp->bid;
node->right = removeNode(node->right, temp->bid.bidId);
}
}
return node;
}
//============================================================================
// Static methods used for testing
//============================================================================
/**
* Display the bid information to the console (std::out)
*
* @param bid struct containing the bid info
*/
void displayBid(Bid bid) {
cout << bid.bidId << ": " << bid.title << " | " << bid.amount << " | "
<< bid.fund << endl;
return;
}
/**
* Load a CSV file containing bids into a container
*
* @param csvPath the path to the CSV file to load
* @return a container holding all the bids read
*/
void loadBids(string csvPath, BinarySearchTree* bst) {
cout << "Loading CSV file " << csvPath << endl;
// initialize the CSV Parser using the given path
csv::Parser file = csv::Parser(csvPath);
// read and display header row - optional
vector<string> header = file.getHeader();
for (auto const& c : header) {
cout << c << " | ";
}
cout << "" << endl;
try {
// loop to read rows of a CSV file
for (unsigned int i = 0; i < file.rowCount(); i++) {
// Create a data structure and add to the collection of bids
Bid bid;
bid.bidId = file[i][1];
bid.title = file[i][0];
bid.fund = file[i][8];
bid.amount = strToDouble(file[i][4], '$');
//cout << "Item: " << bid.title << ", Fund: " << bid.fund << ", Amount: " << bid.amount << endl;
// push this bid to the end
bst->Insert(bid);
}
} catch (csv::Error &e) {
std::cerr << e.what() << std::endl;
}
}
/**
* Simple C function to convert a string to a double
* after stripping out unwanted char
*
* credit: http://stackoverflow.com/a/24875936
*
* @param ch The character to strip out
*/
double strToDouble(string str, char ch) {
str.erase(remove(str.begin(), str.end(), ch), str.end());
return atof(str.c_str());
}
/**
* The one and only main() method
*/
int main(int argc, char* argv[]) {
// process command line arguments
string csvPath, bidKey;
switch (argc) {
case 2:
csvPath = argv[1];
bidKey = "98109";
break;
case 3:
csvPath = argv[1];
bidKey = argv[2];
break;
default:
csvPath = "eBid_Monthly_Sales.csv";
bidKey = "98109";
}
// Define a timer variable
clock_t ticks;
// Define a binary search tree to hold all bids
BinarySearchTree* bst = new BinarySearchTree(); //initialized here instead in case user doesn't load bids first
Bid bid;
int choice = 0;
while (choice != 9) {
cout << "Menu:" << endl;
cout << " 1. Load Bids" << endl;
cout << " 2. Display All Bids" << endl;
cout << " 3. Find Bid" << endl;
cout << " 4. Remove Bid" << endl;
cout << " 9. Exit" << endl;
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
//bst = new BinarySearchTree(); //initialized variable when it was declared because other cases attempt
//use it when it may not be initialized (case 2)
// Initialize a timer variable before loading bids
ticks = clock();
// Complete the method call to load the bids
loadBids(csvPath, bst);
//cout << bst->Size() << " bids read" << endl;
// Calculate elapsed time and display result
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 2:
bst->InOrder();
break;
case 3:
ticks = clock();
bid = bst->Search(bidKey);
ticks = clock() - ticks; // current clock ticks minus starting clock ticks
if (!bid.bidId.empty()) {
displayBid(bid);
} else {
cout << "Bid Id " << bidKey << " not found." << endl;
}
cout << "time: " << ticks << " clock ticks" << endl;
cout << "time: " << ticks * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
break;
case 4:
bst->Remove(bidKey);
break;
}
}
cout << "Good bye." << endl;
return 0;
}
The problem is that your binary search tree is not a balanced search tree. If the input is already sorted on bidId, then your binary tree will basically become a very long linked list. Since you are using recursion, this means that it needs to recurse as many times as there are items in the tree.
The solution is either to make your search tree balanced, or to change your functions to use iteration instead of recursion. The latter is easier, but it will still mean you will have bad performance if you have very unbalanced trees.