// Created by Igor Markov on April 17, 2001
// A simple tree class to demonstrate
//  (a) tree destructors
//  (b) debugging trees using a static counter and object Ids.
// Run this program and see in which order the nodes get destructed
// Draw the tree on paper and make sure you understand why the nodes
// are destructed in that order

#include <iostream>

struct TreeNode
{
    static int counter; // this member is shared by all objects of the class
                   // (C++ requires that it be initialized outside the class)
    int id;             // the id is created at ctruction and never changed
    double val;         // whatever (not used in this example)
    TreeNode * left, * right;  // children

    TreeNode():val(0),left(0),right(0), id(-100)
       { 
         id=counter++;  
         cout << " Created a tree node with id " << id << endl; 
       }
   ~TreeNode() { 
                 if (left)  { delete left;  left=0;  } // paranoia to prevent
                 if (right) { delete right; right=0; } // double deletes
                 // note that both delete calls are recursive, since
                 // delete on a pointer to class calls the dtor of that class
                 cout << " Deleted tree node object with id " << id << endl;
               }
};

int TreeNode::counter=10;

class Tree
{
    public:
     TreeNode* root;
     Tree(): root(0) {}
     Tree(unsigned n): root(0)   // this populates the tree with N nodes
         {                       // (essentially a linked list)
           unsigned i=1;        
           if (n==0) return;
           root=new TreeNode;
           TreeNode* tmp=root;
           for(;i!=n; i++) 
           { tmp->left=new TreeNode; 
             tmp=tmp->left; 
           }
           cout << "Tree created " << endl;
         }
    ~Tree()  
         { 
           if (root) { delete root; root=NULL; }   
                                  // paranoia to preven double delete calls
           cout << "Tree deleted " << endl;
         }
};

int main()
{  
    Tree t(10);   // this tree is statically allocated, and will be
                  // automagically destructed when goes out of scope
    TreeNode *pt=new TreeNode;
    t.root->right=pt;
}