How to delete children of a tree

Question

I need to delete all children of my prefix tree except the root. I'm not asking any code. I just need a method to traverse and delete all children of a tree.

Answer 1

You can use post order traversal to traverse the tree and delete the nodes as:

function deleteTree(node, tree_root) {
     if (node != null) {
         // recursively delete left sub-tree.
         deleteTree(node->left, tree_root);

         // recursively delete right sub-tree.
         deleteTree(node->right, tree_root);

         // time to delete the node..but only if it's not root.
         if( node != tree_root) {
              delete node;
         }  
     }
}

and call the above function as:

deleteTree(root,root);

Answer 2

Write a method delete, which takes a tree node:

 for each child in node
   call delete on child
   remove child from node
   free child

For each child of root call this delete method.

Answer 3

Interesting, by you may do some elegant - tree may not be used after deletion, so you may write a destructor of a node:

struct Node // Non-copyable!
{
  Node *left, *right;

  Node()
    : left(NULL)
    , right(NULL)
  {
  }
  ~Node()
  {
    delete left;
    delete right;
  }
};

And that's all! You use it: delete root. Note that you may not test for NULL before delete because it works well (just return) by C++ standard.