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.

recursive destruction and 170 000 nodes sounds like you might be overflowing the stack. — user4581301, Jul 29 '20 at 14:37
The destruction happens in the destructor, not in that loop. And the destruction is recursive. — Blindy, Jul 29 '20 at 14:40
Tree structures should never be deleted recursively, instead of that the root node should collect all the descendants in a nonrecursive way, clear their `children` vector and then delete those nodes. — t.niese, Jul 29 '20 at 15:05
@t.niese Should I have a `remove` methods to do that ? I need to be able to delete all nodes, not only the root. Then this method would collect all its children and then call the destructor of each one (which would be empty) ? — CptnRad, Jul 30 '20 at 08:02

score 1 · Answer 1 · 2020-08-17T08:48:58.460

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.

Sorry, but this is not good code. In C++, `new` pairs with `delete`, constructors with destructors. Your destructor doesn't work and you need an extra `deleteRoot`. The idea is reasonable enough, it just should be integrated into `Node::~Node`. For this you need to make sure that the `delete node` doesn't trigger a recursive delete, by clearing `node->children` after you've added them to `deleteQueue`. — MSalters, Aug 17 '20 at 08:05
@MSalters You are right and thanks for the feedback, corrected the program based on your comment. — , Aug 17 '20 at 08:49
You don't really need the `is_root`. If `deleteTree` clears the children of `node` before `delete node`, then the recursive call via `delete node` to `node->deleteTree` is a no-op. — MSalters, Aug 17 '20 at 09:04

Segmentation fault when deleting

1 Answers1