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