CODEWITHSUNDEEP
c++algorithmrecursiontreebinary-tree
user2378481
user2378481

Reputation: 839

Recursive Post-order Traversal Deallocating Binary Tree Nodes

I am having trouble deallocating binary tree nodes using post-order traversal in recursive function.

This is part of my struct.. My tree deconstructor will deallocate starting from the root

struct Node {
    Base * data;
    Node * left, * right, *parent;
    static long occupancy;
    long balance;
    long height;

    Node (Base * element) : data (element), left (0), right (0),
        parent (0), balance (0), height(0) {

         occupancy++;
    }


    ~Node (void) {

        deleteNodes();

    }

    void deleteNodes (void) {

        if(height == 0)
            return;

        if(left)
            left->deleteNodes();
        if(right)
            right->deleteNodes();

        if(left)
            delete left;
        if(right)
            delete right;

        delete data;


    }
}

Upvotes: 2

Views: 3000

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55599

You don't need to recursively delete the nodes (and it is likely to cause problems if you do as you'd be trying to delete the pointers multiple times) - the destructors will automatically (recursively) get called if you delete the children.

~Node (void) {
   if (left)
      delete left;
   if (right)
      delete right;
   delete data;
}

Upvotes: 3

yfan
yfan

Reputation: 101

For recursive traversals, you always pass in the root of the tree as the argument. 

void deleteNodes(Node *rover) {
    //**check if rover is nullptr
    deleteNodes(rover->left);
    deleteNodes(rover->right);
    //... 
}

**you won't need to check if rover->left and rover->right are nullptr, because you check it in the beginning of the function.

Hope it helps.

Upvotes: 1

Related Questions