C++ Program to Implement a Binary Search Tree

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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