C++ Binary Search Tree Class

7 min read Jul 01, 2024

C++ Binary Search Tree Class

A binary search tree (BST) is a data structure that allows for efficient searching, insertion, and deletion of elements. It is based on the concept of a binary tree where each node has a key value, and the left subtree contains nodes with keys less than the current node's key, while the right subtree contains nodes with keys greater than the current node's key.

This article will guide you through implementing a C++ class for a binary search tree, providing basic operations like insertion, deletion, searching, and traversal.

Class Structure

#include 

template 
class BST {
private:
    struct Node {
        T data;
        Node *left;
        Node *right;

        Node(const T& val) : data(val), left(nullptr), right(nullptr) {}
    };

    Node *root;

    // Helper functions for insertion, deletion, and traversal
    Node* insert(Node* node, const T& val);
    Node* remove(Node* node, const T& val);
    Node* findMin(Node* node);
    void inorderTraversal(Node* node);
    void preorderTraversal(Node* node);
    void postorderTraversal(Node* node);

public:
    BST() : root(nullptr) {}
    ~BST();

    void insert(const T& val);
    void remove(const T& val);
    bool search(const T& val);
    void inorder();
    void preorder();
    void postorder();
};

Implementation Details

1. Private Members

Node: A nested struct representing a node in the tree. It contains:
- data: The data value stored in the node.
- left: Pointer to the left child node.
- right: Pointer to the right child node.
root: Pointer to the root node of the tree.

2. Helper Functions

insert(Node node, const T& val):* This recursive function inserts a new node with the given value into the tree. It starts from the provided node, compares the value with the current node's data, and recursively inserts it into the left subtree if it's smaller or the right subtree if it's larger.
remove(Node node, const T& val):* This recursive function removes a node with the given value from the tree. It handles different cases based on the node's children:
- Leaf node: Simply delete the node.
- One child: Replace the node with its child.
- Two children: Find the inorder successor (minimum value in the right subtree), replace the node's data with it, and recursively remove the successor node.
findMin(Node node):* This recursive function finds the node with the minimum value in the subtree rooted at the provided node.
inorderTraversal(Node node):* This recursive function performs an inorder traversal of the tree, visiting nodes in ascending order of their values.
preorderTraversal(Node node):* This recursive function performs a preorder traversal of the tree, visiting the root node first, then the left subtree, and finally the right subtree.
postorderTraversal(Node node):* This recursive function performs a postorder traversal of the tree, visiting the left subtree first, then the right subtree, and finally the root node.

3. Public Members

BST(): Constructor, initializing the root to nullptr.
~BST(): Destructor, responsible for deallocating memory occupied by the tree nodes.
insert(const T& val): Calls the insert helper function to insert a new node with the given value into the tree.
remove(const T& val): Calls the remove helper function to remove a node with the given value from the tree.
search(const T& val): This function searches for a node with the given value in the tree and returns true if found, false otherwise.
inorder(): Calls the inorderTraversal helper function to perform an inorder traversal of the tree.
preorder(): Calls the preorderTraversal helper function to perform a preorder traversal of the tree.
postorder(): Calls the postorderTraversal helper function to perform a postorder traversal of the tree.

Example Usage

int main() {
    BST tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(2);
    tree.insert(4);

    std::cout << "Inorder traversal: ";
    tree.inorder();
    std::cout << std::endl;

    std::cout << "Search for 4: " << tree.search(4) << std::endl;

    tree.remove(3);

    std::cout << "Inorder traversal after removal: ";
    tree.inorder();
    std::cout << std::endl;

    return 0;
}

Output

Inorder traversal: 2 3 4 5 7
Search for 4: 1
Inorder traversal after removal: 2 4 5 7

This example demonstrates the basic functionalities of the BST class, including insertion, deletion, searching, and traversal. You can extend this class further by adding more operations like finding the minimum/maximum value, calculating the height, determining if the tree is balanced, etc.

The BST class provides a powerful and efficient way to store and manipulate sorted data in C++.

C++ Binary Search Tree Class