title: C++ stack overflow when using a binary search tree
body: <p>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)...</p>
  <pre><code>#include &lt;iostream&gt;
  #include &lt;time.h&gt;
  
  #include &quot;CSVparser.hpp&quot;
  
  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-&gt;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-&gt;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-&gt;addNode(root, bid);
      }
  }
  
  
   //Remove a bid
  void BinarySearchTree::Remove(string bidId) {
      // FIXED (4a) Implement removing a bid from the tree
      //removes requested node
      this-&gt;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-&gt;bid.bidId) == 0) {
              return current-&gt;bid;
          }
  
          //bid parameter is less than current bid, continues searching to the left
          if (bidId.compare(current-&gt;bid.bidId) &lt; 0) {
              current = current-&gt;left;
          }
          else { //bid parameter is greater than current bid, continues searching to the right
              current = current-&gt;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-&gt;bid.bidId) &lt; 0) {
          if (node-&gt;left == nullptr) { //if left node is null then it adds the new node here
              node-&gt;left = new Node(bid);
          }
          else {
              this-&gt;addNode(node-&gt;left, bid); //recursively calls addnode until bottom is reached
          }
      }
      else { //add to right
          if (node-&gt;right == nullptr) { //if left node is null then it adds the new node here
              node-&gt;right = new Node(bid);
          }
          else {
              this-&gt;addNode(node-&gt;right, bid); //recursively calls addnode until bottom is reached
          }
      }
  }
  void BinarySearchTree::inOrder(Node* node) {
      if (node != nullptr) {
          inOrder(node-&gt;left);
  
          cout &lt;&lt; node-&gt;bid.bidId 
               &lt;&lt; &quot;: &quot; 
               &lt;&lt; node-&gt;bid.title 
               &lt;&lt; &quot; | &quot; 
               &lt;&lt; node-&gt;bid.amount 
               &lt;&lt; &quot; | &quot;
               &lt;&lt; node-&gt;bid.fund 
               &lt;&lt; endl;
  
          inOrder(node-&gt;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-&gt;bid.bidId) &lt; 0) {
          node-&gt;left = removeNode(node-&gt;left, bidId);
      }
      else if (bidId.compare(node-&gt;bid.bidId) &gt; 0) { //if bid parameter is greater than current node, searches right recursively
          node-&gt;right = removeNode(node-&gt;right, bidId);
      }
      else { //if its not &lt; or &gt; then its ==, so it needs to be removed since it matches the parameter bidId
          //no children so node can just be removed
          if ((node-&gt;left == nullptr) &amp;&amp; (node-&gt;right == nullptr)) {
              delete node;
              node = nullptr;
          }
  
          //if one child to left
          if ((node-&gt;left != nullptr) &amp;&amp; (node-&gt;right == nullptr)) {
              Node* temp = node;
              node = node-&gt;left;
              delete temp;
          } //if one child to right
          else if ((node-&gt;left == nullptr) &amp;&amp; (node-&gt;right != nullptr)) {
              Node* temp = node;
              node = node-&gt;left;
              delete temp;
          } //if two children
          else {
              Node* temp = node;
              node = node-&gt;right;
  
  
              while (temp-&gt;left != nullptr) {
                  temp = temp-&gt;left;
              }
  
              node-&gt;bid = temp-&gt;bid;
              node-&gt;right = removeNode(node-&gt;right, temp-&gt;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 &lt;&lt; bid.bidId &lt;&lt; &quot;: &quot; &lt;&lt; bid.title &lt;&lt; &quot; | &quot; &lt;&lt; bid.amount &lt;&lt; &quot; | &quot;
              &lt;&lt; bid.fund &lt;&lt; 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 &lt;&lt; &quot;Loading CSV file &quot; &lt;&lt; csvPath &lt;&lt; endl;
  
      // initialize the CSV Parser using the given path
      csv::Parser file = csv::Parser(csvPath);
  
      // read and display header row - optional
      vector&lt;string&gt; header = file.getHeader();
      for (auto const&amp; c : header) {
          cout &lt;&lt; c &lt;&lt; &quot; | &quot;;
      }
      cout &lt;&lt; &quot;&quot; &lt;&lt; endl;
  
      try {
          // loop to read rows of a CSV file
          for (unsigned int i = 0; i &lt; 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 &lt;&lt; &quot;Item: &quot; &lt;&lt; bid.title &lt;&lt; &quot;, Fund: &quot; &lt;&lt; bid.fund &lt;&lt; &quot;, Amount: &quot; &lt;&lt; bid.amount &lt;&lt; endl;
  
              // push this bid to the end
              bst-&gt;Insert(bid);
          }
      } catch (csv::Error &amp;e) {
          std::cerr &lt;&lt; e.what() &lt;&lt; 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 = &quot;98109&quot;;
          break;
      case 3:
          csvPath = argv[1];
          bidKey = argv[2];
          break;
      default:
          csvPath = &quot;eBid_Monthly_Sales.csv&quot;;
          bidKey = &quot;98109&quot;;
      }
  
      // 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 &lt;&lt; &quot;Menu:&quot; &lt;&lt; endl;
          cout &lt;&lt; &quot;  1. Load Bids&quot; &lt;&lt; endl;
          cout &lt;&lt; &quot;  2. Display All Bids&quot; &lt;&lt; endl;
          cout &lt;&lt; &quot;  3. Find Bid&quot; &lt;&lt; endl;
          cout &lt;&lt; &quot;  4. Remove Bid&quot; &lt;&lt; endl;
          cout &lt;&lt; &quot;  9. Exit&quot; &lt;&lt; endl;
          cout &lt;&lt; &quot;Enter choice: &quot;;
          cin &gt;&gt; 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 &lt;&lt; bst-&gt;Size() &lt;&lt; &quot; bids read&quot; &lt;&lt; endl;
  
              // Calculate elapsed time and display result
              ticks = clock() - ticks; // current clock ticks minus starting clock ticks
              cout &lt;&lt; &quot;time: &quot; &lt;&lt; ticks &lt;&lt; &quot; clock ticks&quot; &lt;&lt; endl;
              cout &lt;&lt; &quot;time: &quot; &lt;&lt; ticks * 1.0 / CLOCKS_PER_SEC &lt;&lt; &quot; seconds&quot; &lt;&lt; endl;
              break;
  
          case 2:
              bst-&gt;InOrder();
              break;
  
          case 3:
              ticks = clock();
  
              bid = bst-&gt;Search(bidKey);
  
              ticks = clock() - ticks; // current clock ticks minus starting clock ticks
  
              if (!bid.bidId.empty()) {
                  displayBid(bid);
              } else {
                  cout &lt;&lt; &quot;Bid Id &quot; &lt;&lt; bidKey &lt;&lt; &quot; not found.&quot; &lt;&lt; endl;
              }
  
              cout &lt;&lt; &quot;time: &quot; &lt;&lt; ticks &lt;&lt; &quot; clock ticks&quot; &lt;&lt; endl;
              cout &lt;&lt; &quot;time: &quot; &lt;&lt; ticks * 1.0 / CLOCKS_PER_SEC &lt;&lt; &quot; seconds&quot; &lt;&lt; endl;
  
              break;
  
          case 4:
              bst-&gt;Remove(bidKey);
              break;
          }
      }
  
      cout &lt;&lt; &quot;Good bye.&quot; &lt;&lt; endl;
  
      return 0;
  }
  </code></pre>