C++ Binary Search Tree Destructor

This tutorial will discuss creating a destructor for a binary search tree using the delete keyword in C++.

C++ Binary Search Tree Destructor

A binary search tree (BST) is a data structure that stores sorted data that can be searched. A binary search tree is used in data centers and software.

Telephone Directory Project In C++ ...
Telephone Directory Project In C++ with Source code Free Download 2020 | C++ Projects

A binary search tree consists of nodes, and each node has two children. When a binary tree is built, the first value represents the root node, and the next value will be placed to its right if it is larger than the root node; otherwise, it will be placed to its left.

When the next value comes, we have to compare it with the root node first, and then we will compare it with other children’s if there are any.

Each node of the binary search tree consists of a key and value. The binary search tree is easy to search because it is already sorted.

To build a binary search tree in C++, we can use the int data type for the value and two pointer variables for the left and right nodes along with the this keyword which is used to refer the current variables to the instance of the class. To create the destructor that deletes the entire binary tree, we can use the delete keyword to deallocate the variables’ memory.

We need to deallocate the memory of the left and right nodes to delete the binary search tree. For example, let’s create a public class of binary search tree which will contain two methods, one to build the tree and one to delete it.

See the code below.

#include <iostream>
using namespace std;

class BTreeNode {
public:
    int Treedata;
    BTreeNode* leftNode;
    BTreeNode* rightNode;

    BTreeNode(int Treedata)
    {
        this->Treedata = Treedata;
        this->leftNode = NULL;
        this->rightNode = NULL;
    }
    ~BTreeNode()
    {

        delete leftNode;
        delete rightNode;
        cout << "Deleting " << this->Treedata << endl;
    }
};

int main()
{
    BTreeNode* root = new BTreeNode(1);
    BTreeNode* node1 = new BTreeNode(2);
    BTreeNode* node2 = new BTreeNode(3);

    root->leftNode = node1;
    root->rightNode = node2;

    delete root;

    return 0;
}

Output:

Deleting 2
Deleting 3
Deleting 1

In the above code, we created a tree with a root and two nodes and deleted it using the delete keyword. We also used the cout() function to display the values of the nodes that are being deleted one by one.

In the above output, we can see that node2 is deleted first because it is the left node, and we deleted the left node first inside the destructor of the binary search tree.

Related Article - C++ Data Structure

  • Implement Circular Array in C++
  • Stack Data Structure Using Linked List in C++
  • Binary Search Tree Insertion in C++