How to ensure correct destructing of a non-regular tree?

I need a function that parses a string to create a non-regular tree and returns a pointer to its root. In the case of a parsing error, an exception is thrown. My current attempt leaks memory. How to destruct the whole tree?

What follows is a minimal reproducible example, omitting the parsing and simulating an error:

#include <iostream>
#include <vector>

template <class T>
struct TreeNode {
    T data;
    std::vector<TreeNode*> children;
    TreeNode(const T& d = T(), const std::vector<TreeNode*>& ch = {})
        : data(d)
        , children(ch)
    {}
};

template <class T>
void destruct(TreeNode<T>*& root) {
    if (!root) return;
    destructRec(root);
    root = nullptr;
}

template <class T>
void destructRec(TreeNode<T>*& root) {
    for (TreeNode<T>* child : root->children) {
        destructRec(child);
    }
    delete root;
    std::cout << "delete TreeNode\n";
}

// create subtree as a child of the initial tree
// Note: In the real code, createTree is recursive; this represents
//       the recursive call.
TreeNode<int>* createSubtree() {
    TreeNode<int>* root = new TreeNode<int>(4);
    if (true) { // simulate error in order to throw exception
        // if I call destruct(root) on this line, 
        // only the subtree will be destructed 
        throw std::logic_error("bad expression");
    }
    return root;
}

// create initial tree
TreeNode<int>* createTree() {
    TreeNode<int>* root = new TreeNode<int>(2);
    TreeNode<int>* child = createSubtree();
    root->children.push_back(child);
    return root;
}

int main() {
    TreeNode<int>* root = createTree();
    destruct(root); // by throwing exeption that line is not executed
    return 0;
} 

I simulate an error in function createSubtree().

Firstly, I call destruct(root) and then throw an exception. But by this way, only the subtree will be destructed. How can I destruct the whole tree?

If I follow your logic with manual new/delete, createTree must catch the exception and requires the destruction, all cannot be done in createSubtree as it is.

Of course if createSubtree is recursive it has to also catch the exception to manage it then throw it again.

If I change a little your proposal adding a parameter to not produce the exception in the first call of createSubtree and to have it recursive for a more realistic case :

#include <iostream>
#include <vector>

template <class T>
struct TreeNode {
    T data;
    std::vector<TreeNode*> children;
    TreeNode(const T& d = T(), const std::vector<TreeNode*>& ch = {})
        : data(d)
        , children(ch)
    {}
};

template <class T>
void destruct(TreeNode<T>*& root) {
    if (!root) return;
    destructRec(root);
    root = nullptr;
}

template <class T>
void destructRec(TreeNode<T>*& root) {
    for (TreeNode<T>* child : root->children) {
        destructRec(child);
    }
    delete root;
    std::cout << "delete TreeNode\n";
}

// create subtree as a child of the initial tree
TreeNode<int>* createSubtree(int v) {
    if (!v) { 
      // simulate error in order to throw exception
      // if I call destruct(root) on that line, 
      // only the subtree will be destructed 
      throw std::logic_error("bad expression");
    }
    
    TreeNode<int>* root = new TreeNode<int>(v);
    
    try {
      root->children.push_back(createSubtree(v-1));
    }
    catch (const std::logic_error&) {
      destruct(root);
      throw;
    }
      
    return root;
}

// create initial tree
TreeNode<int>* createTree(int v) {
  TreeNode<int>* root = new TreeNode<int>(v);
  
  try {
    root->children.push_back(createSubtree(v));
  }
  catch (const std::logic_error&) {
    destruct(root);
    return nullptr;
  }
  return root;
}

int main() {
  TreeNode<int>* root = createTree(4);
  
  destruct(root);
  return 0;
} 

Compilation and execution with valgrind to check memory leaks :

bruno@raspberrypi:/tmp $ g++ -g -Wall c.cpp 
bruno@raspberrypi:/tmp $ valgrind ./a.out 
==33044== Memcheck, a memory error detector
==33044== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==33044== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==33044== Command: ./a.out
==33044== 
delete TreeNode
delete TreeNode
delete TreeNode
delete TreeNode
delete TreeNode
==33044== 
==33044== HEAP SUMMARY:
==33044==     in use at exit: 0 bytes in 0 blocks
==33044==   total heap usage: 13 allocs, 13 frees, 74,647 bytes allocated
==33044== 
==33044== All heap blocks were freed -- no leaks are possible
==33044== 
==33044== For lists of detected and suppressed errors, rerun with: -s
==33044== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
bruno@raspberrypi:/tmp $ 

But as you can see createTree does a lot of work already done in createSubtree, and supposing you just want to return a null pointer in case of an error you can simplify to have :

// create initial tree
TreeNode<int>* createTree(int v) {
  try {
    return createSubtree(v);
  }
  catch (const std::logic_error& ex) {
    return nullptr;
  }
}

---

Additional remarks:

• It is much better to not have destruct and destructRec but just the destructor defined on TreeNode.
• Because TreeNode can contain pointers, to assign or copy a TreeNode will have bad consequences if you do not implement them or avoid them.
• Rather than to do your memory management by hand you can also use unique_ptr for instance.

Example defining the destructor in place of destruct and destructRec :

#include <iostream>
#include <vector>

template <class T>
struct TreeNode {
    T data;
    std::vector<TreeNode*> children;
    TreeNode(const T& d = T(), const std::vector<TreeNode*>& ch = {})
        : data(d)
        , children(ch)
    {}
    ~TreeNode();
};

template <class T>
TreeNode<T>::~TreeNode<T>() {
  for (TreeNode<T>* child : children) {
    delete child;
  }
  std::cout << "delete TreeNode\n";
}

// create subtree as a child of the initial tree
TreeNode<int>* createSubtree(int v) {
    if (!v) { 
      // simulate error in order to throw exception
      // if I call destruct(root) on that line, 
      // only the subtree will be destructed 
      throw std::logic_error("bad expression");
    }
    
    TreeNode<int>* root = new TreeNode<int>(v);
    
    try {
      root->children.push_back(createSubtree(v-1));
    }
    catch (const std::logic_error&) {
      delete root;
      throw;
    }
      
    return root;
}

// create initial tree
TreeNode<int>* createTree(int v) {
  try {
    return createSubtree(v);
  }
  catch (const std::logic_error&) {
    return nullptr;
  }
}


int main() {
  TreeNode<int>* root = createTree(4);
  
  delete root;
  return 0;
} 

But again to use a smart pointer makes your code shorter and more sure :

#include <iostream>
#include <vector>
#include <memory>

template <class T>
struct TreeNode {
    T data;
    std::vector<std::unique_ptr<TreeNode>> children;
    
    TreeNode(const T& d = T()) : data(d) {}
    ~TreeNode();
};

template <class T>
TreeNode<T>::~TreeNode<T>() {
  std::cout << "delete TreeNode\n";
}

// create subtree as a child of the initial tree
std::unique_ptr<TreeNode<int>> createSubtree(int v) {
    if (!v) { 
      // simulate error in order to throw exception
      // if I call destruct(root) on that line, 
      // only the subtree will be destructed 
      throw std::logic_error("bad expression");
    }
    
    std::unique_ptr<TreeNode<int>> root = std::make_unique<TreeNode<int>>(v);
    
    root->children.push_back(std::move(createSubtree(v-1)));
    return root;
}

// create initial tree
std::unique_ptr<TreeNode<int>> createTree(int v) {
  try {
    return createSubtree(v);
  }
  catch (const std::logic_error&) {
    return nullptr;
  }
}


int main() {
  std::unique_ptr<TreeNode<int>> root = createTree(4);
  
  return 0;
} 

and

bruno@raspberrypi:/tmp $ g++ -Wall ccc.cpp
bruno@raspberrypi:/tmp $ valgrind ./a.out 
==35925== Memcheck, a memory error detector
==35925== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==35925== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==35925== Command: ./a.out
==35925== 
delete TreeNode
delete TreeNode
delete TreeNode
delete TreeNode
==35925== 
==35925== HEAP SUMMARY:
==35925==     in use at exit: 0 bytes in 0 blocks
==35925==   total heap usage: 8 allocs, 8 frees, 74,039 bytes allocated
==35925== 
==35925== All heap blocks were freed -- no leaks are possible
==35925== 
==35925== For lists of detected and suppressed errors, rerun with: -s
==35925== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
bruno@raspberrypi:/tmp $ 

Having started programming a long time ago, I have always used new/delete to manage memory, first because there was no choice, then considering that I was mature enough to do it, which is the case by the way. Being also somewhat stubborn (yes yes) I really didn't see what I would gain by using smart pointers. I only went through it very recently while preparing an answer that I was finally unable to give, the question being closed. As you can see for yourself by comparing the latest version with the previous ones, even if the smart pointers are verbose (std::unique_ptr<T> v rather than T * v, std::make_unique<T>rather than new, more the td::move() rather than nothing) the final code is shorter and clearer, and safer. So I strongly advise you to use them.