C++ Vector in Heap Memory results in Segmentation Fault

Question

I am new to C++, and I'm sure this question must be easy to handle but I think I miss some main concepts. In the code, a Binary Tree is implemented, and we are asked to determine the number of nodes in that Binary Tree. As you can see in Node class, a Node has two member pointers: left that points to the Node at left, right that points to the Node at right. The input is the root node. Anyway, I found a solution like this:

Make a vector of Nodes, which I named nodes in the code, and append the root Node, and set the number of nodes (howManyNodes in the code) to 1.
While nodes is not empty (at the beginning we add the root node), check if it has a left and a right pointer. If they are available (i.e., not nullptr) , add those pointers to the vector of nodes (I use insert). At the same time, increase the number of nodes (howManyNodes in the code) by one.
After checking a if specific node has a left and right pointers, I remove that node from the list, for which I use pop_back() function.
At the end, the vector will be empty and I will obtain howManyNodes as the answer.

Here is the code, and I only implemented the count function. The rest is from the template.

#include 
#include 


class Node {
public:
  Node *left, *right;
  Node() { left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

// I implement this part
int count(Node *n) {

    int howManyNodes = 1;
    std::vector *nodes = new std::vector;
    nodes->push_back(*n);

    while (!nodes->empty()){

      Node* trial = new Node(nodes->back());
      if (trial->left){
          std::cout << trial->left << std::endl;
          nodes->insert(nodes->begin(), *trial->left);
          howManyNodes += 1;
      }
      if (trial->right){
          std::cout << trial->right << std::endl;
          nodes->insert(nodes->begin(), *trial->right);
          howManyNodes += 1;
      }
      nodes->pop_back();
  }
  return howManyNodes;
}
// I implement this part.


int main() {

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  // This should print a count of six nodes
  std::cout << count(n) << std::endl;

  // Deleting n is sufficient to delete the entire tree
  // because this will trigger the recursively-defined
  // destructor of the Node class.
  delete n;
  n = nullptr;

  return 0;
}

The problem is, I can never get rid of segmentation fault. As I searched, it happens when the code is trying to access a memory it is not supposed to. My code might be easy to fix, but I have the following questions:

If std::vector uses heap memory for its members, why do I need to define a new vector here? In the main function (which I didn't write) everything is written by new, then I assumed I should also use new whenever possible but I don't understand the logic behind.
In my code, I want to use references, because I want to access only the pointers of Nodes and not modifying them - I learned that using the object itself requires making copies and slows down the process, so not preferable -. What part of my code is trying to modify any pointers?
Now that I defined a new vector, should I also delete it and make it equal to nullptr, before returning the value?

Thanks in advance!

pptaszni · Accepted Answer

The problem with your Node class is that it doesn't follow the rule of 3/5/0 and whenever you make a copy of a Node, and you are making a lot of copies, you have a trouble, because the left right nodes will be deleted once the copied object goes out of scope, and then again when you call delete yourself.

Short summary of bugs in your count implementation:

int count(Node *n) {
    int howManyNodes = 1;
    // doesn't make sense to allocate vector dynamically
    // also you forgot to delete it
    std::vector *nodes = new std::vector;
    // keeping nodes as value will copy them, which leeds to double free
    nodes->push_back(*n);
    while (!nodes->empty()){
      // another copy - thus another problem, but this time "only" a memory leak since you don't delete it
      Node* trial = new Node(nodes->back());
      if (trial->left){
          std::cout << trial->left << std::endl;
          // another copy
          nodes->insert(nodes->begin(), *trial->left);
          howManyNodes += 1;
      }
      if (trial->right){
          std::cout << trial->right << std::endl;
          // another copy
          nodes->insert(nodes->begin(), *trial->right);
          howManyNodes += 1;
      }
      nodes->pop_back();
  }
  return howManyNodes;
}

How it might be implemented without copying any objects:

void count(Node* n, int& numNodes)
{
  numNodes++;
  Node* left = n->left;
  Node* right = n->right;
  if (left) count(left, numNodes);
  if (right) count(right, numNodes);
}

int main() {

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();
  int numNodes{0};
  count(n, numNodes);
  std::cout << numNodes << std::endl;
  delete n;
  return 0;
}

It is a recursive approach, so maybe not the best. If you really need to implement some kind of a tree by hand, use std::unique_ptr, delete explicitly the copy constructor/assignment, and implement the method count inside your Tree class, if you plan to have sth like that.

C++ Vector in Heap Memory results in Segmentation Fault

Answers (2)

Related Questions