Segmentation fault when deleting

Question

I'm fairly new to C++ and I'm trying to implement a tree structure but I'm stuck with a segmentation fault which appears when the tree is deleted. The piece of code is pretty simple, I have a class Node, which contain pointers to its children.

#include <vector>

class Node
{
public:
    int data1, data2;
    std::vector<Node*> children;
    Node* add_child(double data1, double data2) 
    { 
        Node* n = new Node(data1, data2);
        children.push_back(n); 
        return n;
    }
    Node(double data1, double data2)
        :data1(data1), data2(data2)
    { }
    ~Node() 
    {
        for(auto child : children)
        {
            delete child;
        }
        children.clear();
    }
};

int main()
{
    Node root = Node(0, 0); 
        
    Node* n = &root;
    for(int i = 0; i < NB; ++i)
    {
        n = n->add_child(0, 0);
    }
}

The main create a very simple structure, but it is sufficient to have the error. The seg fault only happened for value of NB greater than 170 000.

Answer 1

Based on the non-recursive program to delete an entire binary tree example we can modify your application as follows:

#include <iostream>

using namespace std;

#include <vector>
#include <queue>

class Node
{
public:
    Node* add_child(double data1, double data2) 
    { 
        Node* n = new Node(data1, data2, false);
        children.push_back(n); 
        return n;
    }
    
    Node(double data1, double data2, bool is_root = true )
        :data1(data1), data2(data2), is_root(is_root)
    {
    }
    
    ~Node() 
    { 
       if( is_root ) deleteTree();
    }
    
    size_t get_num_childs()
    {
        return children.size();
    }
    
    Node* get_child( size_t index )
    {
        return children[index];
    }
    
private:

    /* Non-recursive function to delete an entire tree. */
    void deleteTree() 
    { 
        // Create an empty queue for level order traversal 
        queue<Node *> deleteQueue; 
      
        // Do level order traversal starting from root 
        for( int index = 0; index < children.size(); index++ )
        {
            deleteQueue.push( children[index]);
        }
        
        while( !deleteQueue.empty()) 
        { 
            Node *node = deleteQueue.front(); 
            deleteQueue.pop();
            
            for( int index = 0; index < node->get_num_childs(); index++ )
            {
                // Add all childs to queue for deleting
                deleteQueue.push( node->get_child( index ));
            }
      
            delete node;
        } 
    }

private:
    int data1, data2;
    std::vector<Node*> children;
    bool is_root;
};

int main()
{
    Node root = Node(0, 0); 
        
    Node* n = &root;
    for(int i = 0; i < 17000; ++i)
    {
        n = n->add_child(0, 0);
    }
    
    return 0;
}

As mentioned in comments, recursive call node destructor will cause stack overflow and then segmentation fault.

So for fixing this issue we have to stick with the non-recursive deletion of nodes. Which was done with the support of deleteTree() method. For that internally we build a queue with all Nodes which need to be deleted.