1

The structure of the node is below. 

struct node
{
   int data;
   int noofchilds;
   node *child[n];
   node *parent;
 };

I would appreciate both recursive and non-recursive approaches.

Peter
  • 2,719
  • 4
  • 25
  • 55

4 Answers4

1

Non-recursive version:

struct node {
    struct node *parent;
    unsigned nchild;
    struct node *child[XXX];
    int data;
    };

void deltree(struct node *np)
{
struct node *par;

while (np) {
        /* if this node has any children, start by
        ** "descending" to the highest numbered child and kill that first.
        */
        if (np->nchild--) {
                np = np->child[np->nchild];
                continue;
                }
        /* when we arrive here, *np has no more children left,
        ** so kill it, and step up to its parent
        */
        par = node->parent;
        // if np->child was obtained via malloc() uncomment next line
        // free (np->child);
        free (np);
        np = par;
        }
return;
}
wildplasser
  • 43,142
  • 8
  • 66
  • 109
0

Hope It Helps.

// Program to delete all the nodes of a n-Ary tree ~ coded by Hiren
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Tree template
struct Node {
    int val;
    vector<Node*> children;

    // Init constructor
    Node(int val) {
        this->val = val;
    };
};

// Method to print the tree using preOrder traversal
void printTree(Node* root) {
    if(root) {
        cout<<root->val<<' ';
        for(auto childNode : root->children) {
            printTree(childNode);
        }
    }
}

// #1 Method to delete all the nodes of the n-Ary tree using bfs - O(N) & O(M) : Where M is the maximum number of nodes at any level
void deleteAllNodes(Node*& root) {
    // Edge case: When the tree is empty
    if(!root)
        return;

    queue<Node*> q;
    q.push(root);

    while(!q.empty()) {
        // Take the front node of the queue
        root = q.front(); q.pop();
        
        // Store all its childrens to the queue
        for(auto childNode : root->children) {
            q.push(childNode);
        }

        // Ensurely set the node to nullptr and than delete it else a segmentation fault can occur
        root = nullptr;
        delete root;
    }

}

// #2 Method to delete all the nodes of the n-Ary tree using dfs - O(N) & O(H) : Where H let be the maximum height of the tree
void deleteAllNodes_(Node*& root) {
    // Edge case: When the tree is empty
    if(!root)
        return;

    // Visit each of the children one by one
    for(auto childNode : root->children) {
        deleteAllNodes_(childNode);
    }

    // Ensurely set the node to nullptr and than delete it else a segmentation fault can occur
    root = nullptr; 
    delete root;
}

// Driver code
int main() {
    // Creating tree, connecting nodes and initializing their data
    Node* root = new Node(3);
    root->children.push_back(new Node(5));
    root->children.push_back(new Node(1));
    root->children[0]->children.push_back(new Node(6));
    root->children[0]->children.push_back(new Node(2));
    root->children[0]->children[0]->children.push_back(new Node(10));
    root->children[0]->children[0]->children.push_back(new Node(11));
    root->children[0]->children[0]->children.push_back(new Node(12));
    root->children[0]->children[1]->children.push_back(new Node(7));
    root->children[0]->children[1]->children.push_back(new Node(4));

    // Print call
    printTree(root); cout<<'\n';

    // Deletion call
    deleteAllNodes_(root);    

    return 0;
}
// Link: https://stackoverflow.com/questions/9414290/how-to-delete-a-nary-tree-each-node-has-a-parent-pointer-too-in-it
Hiren Joshi
  • 1
  • 1
0

Remove the node and recursively remove its children.

If you have to remove the complete tree (as your question seems to be), the parent pointer does not matter (and is removed with the removal of the node itself).

Michel Keijzers
  • 15,025
  • 28
  • 93
  • 119
  • yes but if i want to do it iteratively i.e without using a stack or queue, then what could be the approach , i think parent pointer might benefit us that time – Peter Feb 23 '12 at 13:56
  • Normally you start at the root since that is the only node you mostly have direct access too ... and in that case the parent is of no use since you only need to go 'downwards' ... I'm wondering if a iterative solution would help in this. – Michel Keijzers Feb 23 '12 at 13:59
  • node = root; do { if(node->noofchild){ node = node->child[noofchild-1]; else { node->parent->noofchild --; curr = node->parent; free(node); node = curr; } }while(node->parent || (node==root && node)) – Peter Feb 23 '12 at 14:23
0

An iterative algorithm:

Start at the parent node.

Then do the following actions as long as possible:
   if the current node has one or more children: 
      set one of the children nodes as the (next) current node
   else
      delete the current node and use its parent as the (next) current node.
      if the current node was the root node (which has no parent), stop.
jofel
  • 3,297
  • 17
  • 31
  • we cannot stop if current node is root because then only subtree correspoding to only 1 child will be true , but i think my algo below similar to yours will do – Peter Feb 23 '12 at 14:11
  • node = root; do { if(node->noofchild){ node = node->child[noofchild-1]; else { node->parent->noofchild --; curr = node->parent; free(node); node = curr; } }while(node->parent || (node==root && node)) – Peter Feb 23 '12 at 14:15
  • 1
    You are right. My algorithm is only fast draft... Your algorithm seems to have some problems, for example if the tree is empty. I would use node = root; while(node) { if(node->noofchild){ node->noofchild--; node = node->child[node->noofchild]; } else { curr = node->parent; free(node); node = curr; } } – jofel Feb 23 '12 at 14:31
  • we can make a check in starting in tree is empty and returning there itself – Peter Mar 11 '12 at 08:05