C++ Program to Implement a Binary Search Tree

1. Introduction

A Binary Search Tree (BST) is a binary tree data structure where each node has at most two children, referred to as the left child and right child. For a tree to be a binary search tree, the left child node's value must be less than or equal to the parent node's value, and the value of the right child node must be greater than the parent node. 

In this post, we will walk through the implementation of a basic BST in C++.

2. Program Overview

Our BST will have basic operations including insertion, search, and in-order traversal.

Here's a brief overview:

1. Node class: Defines the structure of each node in our BST.

2. BST class: Contains the core functions like insert, search, and inOrderTraversal.

3. The insert function will add new nodes in the appropriate position.

4. The search function will determine if a value exists in the tree.

5. The inOrderTraversal will print the values in ascending order.

3. Code Program

#include<iostream>
using namespace std;

// Definition of a node in the binary search tree
class Node {
public:
    int data;           // Value contained in the node
    Node* left;         // Pointer to the left child
    Node* right;        // Pointer to the right child

    // Constructor to initialize the node with a value and set left and right children to nullptr
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class BST {
private:
    Node* root; // Root node of the tree

    // Recursive function to insert a value into the BST
    Node* insert(Node* node, int val) {
        if (!node) return new Node(val); // Create a new node if current node is nullptr

        // If value is less than or equal to current node's data, insert to left subtree
        if (val <= node->data) {
            node->left = insert(node->left, val);
        } else { // Otherwise, insert to the right subtree
            node->right = insert(node->right, val);
        }

        return node;
    }

    // Recursive function to do in-order traversal of the BST
    void inOrderTraversal(Node* node) {
        if (!node) return; // Base case
        inOrderTraversal(node->left);       // Traverse left subtree
        cout << node->data << " ";          // Process the current node
        inOrderTraversal(node->right);      // Traverse right subtree
    }

    // Recursive function to search for a value in the BST
    bool search(Node* node, int val) {
        if (!node) return false; // Return false if node is nullptr
        if (node->data == val) return true; // Value found

        // If value is less than current node's data, search in left subtree
        if (val <= node->data) return search(node->left, val);
        else return search(node->right, val); // Otherwise, search in right subtree
    }

public:
    BST() : root(nullptr) {} // Constructor initializes root to nullptr

    // Public member to insert a value into the BST
    void insert(int val) {
        root = insert(root, val);
    }

    // Public member to search for a value in the BST
    bool search(int val) {
        return search(root, val);
    }

    // Public member to do in-order traversal of the BST
    void inOrderTraversal() {
        inOrderTraversal(root);
        cout << endl;
    }
};

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

    cout << "In-order Traversal: ";
    tree.inOrderTraversal();

    int num = 4;
    // Check if the value exists in the BST and print the result
    if (tree.search(num)) {
        cout << num << " exists in the BST." << endl;
    } else {
        cout << num << " does not exist in the BST." << endl;
    }

    return 0;
}

Output:

In-order Traversal: 1 3 4 5 7
4 exists in the BST.

4. Step By Step Explanation

1. The Node class represents each node in our BST, containing data, a pointer to the left child, and a pointer to the right child. 

// Definition of a node in the binary search tree
class Node {
public:
    int data;           // Value contained in the node
    Node* left;         // Pointer to the left child
    Node* right;        // Pointer to the right child

    // Constructor to initialize the node with a value and set left and right children to nullptr
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

2. The BST class contains our core functions. 

3. The insert function is recursive and places a new node in its appropriate position based on its value. 

    // Public member to insert a value into the BST
    void insert(int val) {
        root = insert(root, val);
    }

4. The inOrderTraversal function prints values in ascending order. 

    // Public member to do in-order traversal of the BST
    void inOrderTraversal() {
        inOrderTraversal(root);
        cout << endl;
    }

5. The search function checks for the existence of a value in the tree.

    // Public member to search for a value in the BST
    bool search(int val) {
        return search(root, val);
    }

6. In our main function, we create an instance of our BST, insert a few values, and then perform an in-order traversal and a search operation to demonstrate the tree's functionality.

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

    cout << "In-order Traversal: ";
    tree.inOrderTraversal();

    int num = 4;
    // Check if the value exists in the BST and print the result
    if (tree.search(num)) {
        cout << num << " exists in the BST." << endl;
    } else {
        cout << num << " does not exist in the BST." << endl;
    }

    return 0;
}