Binary Search Tree Implementation in CPP

1. Introduction

A Binary Search Tree (BST) is a binary tree with a unique property: for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. This inherent structure allows for efficient insertion, deletion, and search operations. In this blog, we will discuss the implementation of a basic BST in C++.

2. Implementation Steps

1. Define a Node class, which will represent each individual element (or node) in the BST. This class will contain the data and pointers to its left and right children.

2. Create a BST class that will encapsulate the tree's behavior.

3. Implement methods to insert nodes (insert), search for a node (search), and display the tree structure using in-order traversal (inOrderTraversal).

4. Demonstrate the usage of the BST class in a main function.

3. Implementation in C++ Programming

#include<iostream>
class Node {
public:
    int data;           // Data stored in the node
    Node* left;         // Pointer to the left child
    Node* right;        // Pointer to the right child
    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};
class BST {
private:
    Node* root;
    Node* insert(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }
        if (value < node->data) {
            node->left = insert(node->left, value);
        } else {
            node->right = insert(node->right, value);
        }
        return node;
    }
    bool search(Node* node, int value) {
        if (node == nullptr) {
            return false;
        }
        if (node->data == value) {
            return true;
        }
        if (value < node->data) {
            return search(node->left, value);
        } else {
            return search(node->right, value);
        }
    }
    void inOrderTraversal(Node* node) {
        if (node == nullptr) return;
        inOrderTraversal(node->left);
        std::cout << node->data << " ";
        inOrderTraversal(node->right);
    }
public:
    BST() {
        root = nullptr;
    }
    void insert(int value) {
        root = insert(root, value);
    }
    bool search(int value) {
        return search(root, value);
    }
    void displayInOrder() {
        std::cout << "In-Order Traversal: ";
        inOrderTraversal(root);
        std::cout << std::endl;
    }
};
int main() {
    BST bst;
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(20);
    bst.insert(40);
    bst.insert(60);
    bst.insert(80);
    bst.displayInOrder();
    std::cout << "Searching for 25: " << (bst.search(25) ? "Found" : "Not Found") << std::endl;
    std::cout << "Searching for 40: " << (bst.search(40) ? "Found" : "Not Found") << std::endl;
    return 0;
}

Output:

In-Order Traversal: 20 30 40 50 60 70 80
Searching for 25: Not Found
Searching for 40: Found

Explanation:

1. The Node class represents individual elements of the BST. Each node contains data and pointers to its left and right children.

2. The BST class encapsulates the behavior of the binary search tree.

3. insert(Node* node, int value): This is a recursive helper function that inserts a new node with the given value into the tree.

4. search(Node* node, int value): A recursive function that checks if a value exists in the tree.

5. inOrderTraversal(Node* node): A private helper method that recursively traverses the tree in in-order (left, root, right) and prints each node's data.

6. Public member functions (insert, search, displayInOrder) provide interfaces to interact with the BST.

7. main(): Demonstrates the usage of the BST by inserting nodes, displaying them using in-order traversal, and searching for specific values.