Is it necessary to traverse a General Tree for destroying the tree (destructor)?

Question

When destroying(when objects is out of scope) General Tree is it necessary to traverse each node and deleting them like you do with doubly linked list? The General Tree I am writing is a circular so that insertion can be done in constant time. It would be much helpful if someone could help me fix the error. The destructor below currently causes stack overflow( I think it is because of the tree being circular).

Here are the 2 destructors

~Node()
         {
        if(left){delete left;}
                if(next){delete next;}
                if(parent){delete parent;}
          }

for General tree

 ~Gen()
       {
           if (head)
                 delete head; //call destructor on node
                 head = nullptr;
                 m_size = 0;
        }

This is the node class

class Node {
public:
    typedef Node* nodePtr;
    int data;
    //Left child- right sibling implementation
    nodePtr left, next, parent;
    int rank; //will be used for merging.
~Node()
         {
               if(left){delete left;}
                if(next){delete next;}
                if(parent){delete parent;}
          }
        
private:
    
    Node & operator =(const Node&);
};

this is the tree that uses the node above

class Gen{
 public:
      typedef Node* nodePtr;
       Gen():m_size(0),head(0){}
       ~Gen()
       {
           if (head)
                 delete head; //call destructor on node
                 head = nullptr;
                 m_size = 0;
        }
        void push(int val)
        {
        nodePtr newNode = new Node;
        
        newNode->data = val;
        newNode->rank = 0;
        newNode->left = newNode->next = newNode->parent = 0; //set all pointers to null
        insertRoot(newNode); //call the inserthelper
        ++m_size;
        }
        //other functions (deleteMin, decreaseKey etc)
private:
int m_size;
nodePtr head;
nodePtr insertRoot(nodePtr newNode)
{
   //create a circular link
   if (!head)
    {
        head = newNode;
        newNode->next = newNode;
    }
    else
    {
        newNode->next = head->next;
        head->next = newNode;
        if (newNode->data < head->data)  //min heap (lazy insert)
            head = newNode;
    }
}
};

Answer 1

You will need to call the destructor of each of the members of the tree in some way, either by traversing the tree in recursive manner (like your implementation) or by iterative methods.

Simplest iterative approach would be to use a stack and add the elements as you go down the tree, and pop the elements to delete them when you go up the tree. Check more on this approach in this post

So in your specific case, the General Tree will have a distractor to travel trough the tree to destroy the nodes, and you don't need the node destructor. The destructor will look something like:

#include <stack>
...
....
~Gen() {
    std::stack<Node*> s;
    s.push(head);
    Node* current;
    while (!s.empty()) {
        current = s.top();
        s.pop();
        if (current->left != nullptr) {
            s.push(current->left);
        };
        if (current->next != nullptr) {
            s.push(current->next);
        }
        delete current;
    }
    head = nullptr;
}

So, as you are progressing down the tree, you add the children to the stack and you delete the parent. Once the stack is empty, all nodes in the tree are deleted.

Answer 2

Is it necessary to traverse a General Tree for destroying the tree (destructor)?

Yes, it is necessary to visit every node in order to delete them (or at least every branch since you can delete the leaves from branches).

---

I assume that parent of node X points to a such node whose child X is. A problem with your implementation of the node destructor is that destructor of parent deletes its child, and its child deletes the parent which deletes the child which deletes the parent which deletes the child which deletes the parent which deletes the child... Can you spot the problem? The recursion is endless. Besides, the lifetime of the parent has already ended, so the child attempting to delete the parent results in undefined behaviour.

The solution to this is simple: Don't delete parent. If you start from root and delete children, and if parent always points to a node that is already being deleted, then you visit all nodes of a tree as desired.

---

Another problem is that your tree isn't balanced, so the depth of your tree may in worst case be linear in relation to the number of elements. This causes the depth of recursion of your destructor to grow linearly (in worst case) which may lead to stack overflow even if the infinite loops weren't a problem.

You shouldn't use recursion to destroy trees that aren't balanced. You should use trivial destructor for the node, and implement iterative destructor for the tree.

A good algorithm to destroy an unbalanced binary tree is to rotate one subtree until it is null, then delete root and repeat with the other child node. Example (entirely untested, may be buggy):

while (head) {
    if (head->left) {
        // rotate
        Node* temp_left = head->left;
        head->left = head->left->next;
        temp_left->next = head;
        head = temp_left;
    } else {
        Node* temp_next = head->next;
        delete head;
        head = temp_next;
    }
}

---

Tree I am writing is a circular

This also breaks your implementation of the destructor since when you reach a "leaf" pointing back to the root, you will enter similar infinite loop and undefined behaviour described above.

Unfortunately, this property also breaks my suggested iterative destructor. I don't have time now to figure out a good solution though. An idea is to combine it with a cycle detection algorithm.