C++ Binary Search Tree Implementation

MUAZHAN

7 min read

·

Jul 01, 2024

37

Share

C++ Binary Search Tree Implementation

A binary search tree (BST) is a data structure that allows for efficient searching, insertion, and deletion of nodes. It's a tree-based data structure where each node has a key (value) and two child nodes, a left child and a right child. The structure adheres to the following property:

• Left Subtree Property: All nodes in the left subtree of a node have a key value less than the node's key value.
• Right Subtree Property: All nodes in the right subtree of a node have a key value greater than the node's key value.

This property ensures that the tree is ordered, allowing for efficient search operations.

Implementing a C++ Binary Search Tree

Here's a C++ implementation of a binary search tree:

#include 

struct Node {
    int data;
    Node *left;
    Node *right;

    Node(int data) {
        this->data = data;
        left = right = nullptr;
    }
};

class BST {
private:
    Node *root;

public:
    BST() {
        root = nullptr;
    }

    // Insertion
    void insert(int data) {
        root = insert(root, data);
    }

    Node* insert(Node* node, int data) {
        if (node == nullptr) {
            return new Node(data);
        }

        if (data < node->data) {
            node->left = insert(node->left, data);
        } else if (data > node->data) {
            node->right = insert(node->right, data);
        }

        return node;
    }

    // Searching
    bool search(int data) {
        return search(root, data);
    }

    bool search(Node* node, int data) {
        if (node == nullptr) {
            return false;
        }

        if (data == node->data) {
            return true;
        } else if (data < node->data) {
            return search(node->left, data);
        } else {
            return search(node->right, data);
        }
    }

    // Deletion
    void deleteNode(int data) {
        root = deleteNode(root, data);
    }

    Node* deleteNode(Node* node, int data) {
        if (node == nullptr) {
            return nullptr;
        }

        if (data < node->data) {
            node->left = deleteNode(node->left, data);
        } else if (data > node->data) {
            node->right = deleteNode(node->right, data);
        } else {
            // Case 1: Node has no children
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                node = nullptr;
            }
            // Case 2: Node has one child
            else if (node->left == nullptr) {
                Node* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                Node* temp = node->left;
                delete node;
                return temp;
            }
            // Case 3: Node has two children
            else {
                Node* temp = findMin(node->right);
                node->data = temp->data;
                node->right = deleteNode(node->right, temp->data);
            }
        }

        return node;
    }

    Node* findMin(Node* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // Traversal (Inorder)
    void inorderTraversal() {
        inorderTraversal(root);
    }

    void inorderTraversal(Node* node) {
        if (node != nullptr) {
            inorderTraversal(node->left);
            std::cout << node->data << " ";
            inorderTraversal(node->right);
        }
    }
};

int main() {
    BST tree;

    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);

    std::cout << "Inorder Traversal: ";
    tree.inorderTraversal();
    std::cout << std::endl;

    std::cout << "Searching for 40: " << (tree.search(40) ? "Found" : "Not found") << std::endl;

    tree.deleteNode(40);

    std::cout << "Inorder Traversal after deletion: ";
    tree.inorderTraversal();
    std::cout << std::endl;

    return 0;
}

Explanation:

• Node struct: Defines the structure of a node in the tree. It contains the data (key value), left (pointer to the left child), and right (pointer to the right child).
• BST class: Represents the binary search tree.
• insert(data): Inserts a new node with the given data into the tree. The function recursively traverses the tree to find the correct position for the new node.
• search(data): Searches for a node with the given data in the tree. Returns true if found, false otherwise.
• deleteNode(data): Deletes the node with the given data from the tree. Handles different cases based on the number of children the node has.
• findMin(node): Finds the node with the minimum value in the subtree rooted at the given node.
• inorderTraversal(): Performs an inorder traversal of the tree, printing the nodes in ascending order.

This is a basic implementation of a binary search tree in C++. You can further extend it by implementing other operations like finding the maximum, height, etc.

Remember that this is a simple example. In real-world applications, you might want to use more complex algorithms for balancing the tree to maintain optimal performance.