Destructor for Binary Search Tree

Question

I am trying to write the destructor for my Binary Search Tree and I know how to recursively loop through the tree, but I do not know how to do that in the destructor so that every node is deleted.

My Header is:

struct Node;
typedef string TreeType;
typedef Node * TreePtr;

//Defines a Node
struct Node
{
    TreeType Info;
    int countDuplicates = 1;
    TreePtr Left, Right;
};

class Tree
{
public:
    //Constructor
    Tree();

    //Destructor
    ~Tree();

    //Retruns true if the tree is Empty
    bool Empty();

    //Inserts a Node into the tree
    bool Insert(TreeType);

    //Delete decides what type of delection needs to occur, then calls the correct Delete function
    bool Delete(Node * , Node * );

    //Deletes a leaf node from the tree
    bool DeleteLeaf(TreePtr, TreePtr);

    //Deletes a two child node from the tree
    bool DeleteTwoChild(TreePtr);

    //Deletes a one child node from the tree
    bool DeleteOneChild(TreePtr, TreePtr);

    //Finds a certain node in the tree
    bool Find(TreeType);

    //Calculates the height of the tree
    int Height(TreePtr);

    //Keeps a count of the nodes currently in the tree;
    void Counter();

private:

    //Prints the nodes to the output text file in order alphabetically
    void InOrder(ofstream &,TreePtr);

    //Defines a TreePtr called Root
    TreePtr Root;

    //Defines a TreePtr called Current
    TreePtr Current;

    //Defines a TreePtr called Parent
    TreePtr Parent;
};

My constructor is:

Tree::Tree()
{
    Root = NULL;
    Current = NULL;
    Parent = NULL;
}

Is there a way to call the destructor recursively? If not, how do I traverse through every node to delete it.

Dasilva

Imagine if you could call the destructor recursively. The destructor runs with the current object being a Tree, not a Node. And it doesn't take any parameters. So how would it know which node to destruct? – Chime

Answer 1

void Tree::DestroyRecursive(TreePtr node)
{
    if (node)
    {
        DestroyRecursive(node->left);
        DestroyRecursive(node->right);
        delete node;
    }
}

Tree::~Tree()
{
    DestroyRecursive(Root);
}

Strengthen

I did that and I received this error " Build started: Project: BinarySearchTree, Configuration: Debug Win32 ------ BST.cpp BST.obj : error LNK2019: unresolved external symbol "public: void __thiscall Tree::DestroyRecursive(struct Node *)" (?DestroyRecursive@Tree@@QAEXPAUNode@@@Z) referenced in function "public: __thiscall Tree::~Tree(void)" (??1Tree@@QAE@XZ) C:\Users\Matthew\Desktop\Comp245\BinarySearchTree\Debug\BinarySearchTree.exe : fatal error LNK1120: 1 unresolved externals ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========" – Dasilva

I figured it out. I forgot the "Tree::" in the void function. Thanks. @JohnZwinck – Dasilva

@MatthewDanielSorrell: I actually didn't mean for DestroyRecursive to be a member of Tree. You can make it that way if you want, but it can also be a regular free function. – Strengthen

Why don't allow delete operator do all the stuff by itself? look at my response that deletes all nodes but the recursive calll is behind the scenes embedded in the delete operator. – Earphone

@LuisColorado check my comment below your answer – Elsi

Answer 2

You need two destructors:

Tree::~Tree()
{
    delete Root;
}

and

Node::~Node()
{
    delete Left;
    delete Right;
}

But you don't really need two classes here. Every Node is a tree.

Comedian

That makes it hard to do tree operations like removing a single Node, doesn't it? Because it makes every Node deletion recursive. – Strengthen

@JohnZwinck No, you just adjust the node and its surrounding nodes prior to deleting it. For example, if you're deleting the node itself but not its children, you would attach its left and right subtrees to other nodes, clear them in the node itself, then delete the node. – Comedian

Yeah, that's fair. If there's such a strong concept of ownership then maybe smart pointers would be a better design from the beginning. – Strengthen

Answer 3

When you call delete or your Tree goes to end of lifetime (exit from a block, like the example at the end), you have to delete the Tree children Node s and the delete operator will call the destructor, see example at the end.

This will make the Tree disappear entirely from memory when the Tree destructor is called.

Just try this:

#include <iostream>
using namespace std;

class Node {
    Node *left, *right;
public:
    Node(Node *l, Node *r);
    ~Node();
};

class Tree {
    Node *root;
public:
    Tree(Node *rt);
    ~Tree();
};

Tree::Tree(Node *rt):root(rt) {
    cout << "new Tree with root node at " << rt << endl;
}
Tree::~Tree() {
    cout << "Destructor of Tree" << endl;
    if (root) delete root;
}
Node::Node(Node *l, Node *r):left(l), right(r) {
    cout << "Node@"
        << this
        << "(left:" << l
        << ", right:" << r << ")"
        << endl;
}   
Node::~Node() {
    cout << "~Node@" << this 
        << endl;
    if (left) delete left;
    if (right) delete right;
}

int main() {
    Tree t(
        new Node(
            new Node(
                new Node(
                    new Node(0, 0), 
                    0),
                0),
            new Node(0, new Node(0, 0))));
}

Earphone

This is functionally no different from @EJP's prior answer. – Strengthen

but it works even if node has null pointers!!! The main diffference is that this answer is tested and @ejp's is not. It shows the destructor call sequence and how the tree is created and deleted. Also, it allows to locate Tree s in the stack (as shown). – Earphone

Very elegant method. I liked how you only utilized delete. Thank you! – Stealthy

deletes chain recursively in the middle of other deletes.... it's the compiler that knows the exact order of execution. In a parallel environment, those than be handled with multiple threads. – Earphone

If you want to delete only one node from the tree then Node distructor will delete all the nodes below. So this will only work as expected if you don't need to implement a delete method. – Elsi

Answer 4

Here is my implementation. A Tree equals a TreeNode.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    ~TreeNode() {
        delete left;
        delete right;
    }
    ...
};

Simply delete the root node of the tree, then the whole tree will be deleted recursively.

TreeNode* root = new TreeNode(2);
delete root;

You may already know what a delete do.

When delete is used to deallocate memory for a C++ class object, the object's destructor is called before the object's memory is deallocated (if the object has a destructor).

So, in a treeNode's destructor, you only need to destroy the left and right pointers that are manually allocated by you. You don't need to worry about the deallocation of the node itself.

Annulation

Answer 5

The best approach would be to use smart pointers and it will recursively delete for you as the ref count goes to 0:

class TreeNode {
    private:
        TreeType info_;
        unique_ptr<TreeNode> left_, right_;
    public:
        TreeNode(): info_(""), left_(nullptr), right_(nullptr) {}
        TreeNode(TreeType info): info_(info), left_(nullptr), right_(nullptr) {}
};

With modern C++ you should never need to create your own destructor (unless you're creating your own RAII proxy class - rare) and you should also never need to call new / delete.

Cryohydrate

the logic of your comment is incorrect and generally only applies to high level classes or when performance isn't a consideration at all. Smart pointers for the innerworkings of a fundamental data structure like a Tree are overkill and the overhead is brutal to having a performant data structure. Notice that none of the STL containers are defined using smart pointers. The mere statement that you should "never" call new or delete is preposterous, and the same goes for never creating your own destructor. Almost any time you say 'never' you are wrong, and this is not an exception. – Aerostatics

I should’ve been more specific and said “almost never”. Smart pointers didn’t exist when the stl was first created so obviously they weren’t created with smart pointers. And the proper way to solve problems is to prefer to use higher level abstractions. If you want a BST you should use the STL as it already has this in map. The OP said he wanted to create his/her own so next solution should use best practices and use smart pointers. Only go lower level if you have to and from what I’ve seen there is no reason to pre-optimize here. – Cryohydrate

STL has been updated with move semantics.. there's a reason they haven't updated it for smart pointers. for primitive low level data types if you can't manage the memory yourself then dont implement them. many folks who want to learn how to do it are also going to manage memory themselves. It depends on the level at which you are working at. Some folks will embrace create_unique and use unique pointers and some folks will stick to new/delete and manage pointers themselves for low level custom containers. nothing wrong with that. best path is to learn and understand how to operate with both – Aerostatics

Yeah that makes sense. In practice though it's best to try to use smart pointers (it's rare to ever need to make your own data structure though so if you have to do that then yeah chances are you are you need the extra efficiency of raw pointers). I just wouldn't recommend it unless your use case explicitly calls for it. Also if this is for a coding interview or something like that then again unique_ptr would be better as it shows you understand how to use smart pointers which is what we should usually reach for (and it simplifies the code). – Cryohydrate

It's not as rare as you think I do it every day and have for over a decade at multiple firms. It's about context and performance. If you took a code interview where I've worked and suggested using smart pointers for a building a list we would ask you what the expense of that is, what questions you should ask us, and try to hint to you that it's a horrible idea. If you didn't catch on you'd fail. Writing a list without smart pointers is a good academic exercise, writing it with smart pointers is a trivial exercise that is pointless and only tells us next to nothing. – Aerostatics