C++ Program to Implement a Binary Search Tree

Table of Contents

Introduction

A Binary Search Tree (BST) is a popular data structure used to maintain a sorted sequence of elements, providing efficient search, insertion, and deletion operations. In a BST, each node has at most two children, referred to as the left and right child. The left child’s value is less than its parent’s value, and the right child’s value is greater than its parent’s value. This article presents a C++ program to implement a binary search tree, showcasing how to perform common BST operations.

Prerequisites

Before proceeding with the program, it’s important to have:

A basic understanding of C++ programming.
Familiarity with pointers and dynamic memory allocation.
Knowledge of fundamental data structures and algorithms.

With these basics in place, let’s explore the implementation of a binary search tree in C++.

1. Program to Implement a Binary Search Tree

1.1 Program Structure

The program consists of defining the structure of a BST node and implementing functions for insertion, searching, and inorder traversal.

C++

#include <iostream>

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

class BST {
public:
    BST() : root(nullptr) {}

    void insert(int value) {
        root = insertNode(root, value);
    }

    bool search(int value) {
        return searchNode(root, value);
    }

    void inorderTraversal() {
        inorderTraversalNode(root);
        std::cout << std::endl;
    }

private:
    TreeNode* root;

    TreeNode* insertNode(TreeNode* node, int value) {
        if (node == nullptr) {
            return new TreeNode(value);
        }
        if (value < node->value) {
            node->left = insertNode(node->left, value);
        } else {
            node->right = insertNode(node->right, value);
        }
        return node;
    }

    bool searchNode(TreeNode* node, int value) {
        if (node == nullptr) {
            return false;
        }
        if (value == node->value) {
            return true;
        }
        if (value < node->value) {
            return searchNode(node->left, value);
        } else {
            return searchNode(node->right, value);
        }
    }

    void inorderTraversalNode(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        inorderTraversalNode(node->left);
        std::cout << node->value << " ";
        inorderTraversalNode(node->right);
    }
};

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);

    std::cout << "Inorder Traversal of BST: ";
    bst.inorderTraversal();

    int valueToSearch = 40;
    std::cout << "Searching for " << valueToSearch << ": " 
              << (bst.search(valueToSearch) ? "Found" : "Not Found") << std::endl;

    return 0;
}

1.2 Output Explanation

In this example, the BST is structured as follows:

C++

      50
     /  \
    30   70
   / \   / \
  20 40 60 80

The inorder traversal of this tree will be: 20 30 40 50 60 70 80

The search operation will output whether a specific value exists in the BST. For instance, searching for 40 will return “Found”.

2. Binary Search Tree Operations in C++

2.1 Insertion

The insertion operation adds a new node to the BST. The function insertNode recursively finds the correct position for the new node based on its value and inserts it.

C++

TreeNode* insertNode(TreeNode* node, int value) {
        if (node == nullptr) {
            return new TreeNode(value);
        }
        if (value < node->value) {
            node->left = insertNode(node->left, value);
        } else {
            node->right = insertNode(node->right, value);
        }
        return node;
    }

2.2 Search

The search operation checks if a value exists in the BST. The function searchNode recursively traverses the tree to find the target value.

C++

 bool searchNode(TreeNode* node, int value) {
        if (node == nullptr) {
            return false;
        }
        if (value == node->value) {
            return true;
        }
        if (value < node->value) {
            return searchNode(node->left, value);
        } else {
            return searchNode(node->right, value);
        }
    }

2.3 Inorder Traversal

Inorder traversal visits the nodes in ascending order of their values. The function inorderTraversalNode recursively traverses the left subtree, visits the root, and then traverses the right subtree.

C++

void inorderTraversalNode(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        inorderTraversalNode(node->left);
        std::cout << node->value << " ";
        inorderTraversalNode(node->right);
    }

Conclusion

A program to implement a binary search tree in C++ involves defining the tree’s structure and implementing key operations like insertion, search, and traversal. This article provided a clear implementation of these operations. For those looking to further their understanding, it’s beneficial to practice these operations and explore additional ones, such as deletion and balancing the BST