Deleting a binary tree in C++

Help find the memory leak in the following binary tree implementation. Maybe someone is too lazy to dig into such a piece of code)

template <typename T>
class Node
{
 private:
    T data;
    Node<T> *left, *right;
    bool flag;
    friend class Tree<T>;
 public:
    Node(): flag(false), left(NULL), right(NULL){}
    ~Node{if(left) delete left; if(right)delete right}
};

template <typename T>
class Tree
{
 private:
    Node<T>* head;
    Node<T>* AddNode(Node<T>*, T);
    void ViewTree(Node<T>*);
    void DestroyTree(Node<T>*);
 public:
    Tree();
    ~Tree();
    void View();
    void Add(T);
};

template <typename T>
Tree<T>::Tree(): head(NULL){}

template <typename T>
Tree<T>::~Tree()
{
 DestroyTree(head);
}

template <typename T>
void Tree<T>::View()
{
 ViewTree(head);
}

template <typename T>
void Tree<T>::Add(T obj)
{
 head = AddNode(head, obj);
}

template <typename T>
Node<T>* Tree<T>::AddNode(Node<T>* root, T obj)
{
 if(root == NULL)
 {
  root = new Node<T>;
  root->data = obj;
  root->flag = true;
 }
 else
 {
  if(obj < root->data)
  {
   root->left = AddNode(root->left, obj);
  } 
  else 
  {
   root->right = AddNode(root->right, obj);
  }
 }
 return root;
}

template <typename T>
void Tree<T>::ViewTree(Node<T> *root)
{
 if(root->left)
 {
  ViewTree(root->left);
 }
 if(root->flag) cout << root->data << endl;
 if(root->right)
 {
  ViewTree(root->right);
 }
}

template <typename T>
void Tree<T>::DestroyTree(Node<T> *root)
{
 if(root)
 {
  DestroyTree(root->left);
  DestroyTree(root->right);
  delete root;
 }
}

int main()
{
 Tree<int> *tree = new Tree<int>;
 tree->Add(5);
 tree->Add(4);
 tree->Add(2);
 tree->View();
 delete tree;
}

Thank you, if anyone is too lazy to dig into this

Author: Nicolas Chabanovsky, 2012-06-08

1 answers

You don't have a leak, but rather the opposite. You delete the entire subtree recursively both in the DestroyTree and when deleting each node. To get everything right, you either need to remove recursive calls from the ~Node destructor, i.e. just use the default destructor, or remove recursive calls from DestroyTree:

template <typename T>
void Tree<T>::DestroyTree(Node<T> *root)
{
  delete root;
}

Root does not need to be checked for inequality 0, because "delete 0" is an allowed operation.

 3
Author: dzhioev, 2012-06-08 21:56:52