Lecture 300:- Let's code Binary Search Tree

Here's a complete C++ implementation of a Binary Search Tree (BST) with functions to create and insert nodes, perform in-order traversal, and search for a specific key in the BST:

cppCopy code

#include <iostream> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; class BST { private:    TreeNode* root;    // Private recursive function to insert a new node in the BST    TreeNode* insertBST(TreeNode* root, int val) {        if (root == nullptr)            return new TreeNode(val);        if (val < root->val)            root->left = insertBST(root->left, val);        else if (val > root->val)            root->right = insertBST(root->right, val);        return root;    }    // Private recursive function for in-order traversal    void inOrderTraversal(TreeNode* root) {        if (root == nullptr)            return;        inOrderTraversal(root->left);        cout << root->val << " ";        inOrderTraversal(root->right);    }    // Private recursive function to search for a key in the BST    TreeNode* searchBST(TreeNode* root, int key) {        if (root == nullptr || root->val == key)            return root;        if (key < root->val)            return searchBST(root->left, key);        else            return searchBST(root->right, key);    } public:    BST() : root(nullptr) {}    // Public function to insert a new node in the BST    void insert(int val) {        root = insertBST(root, val);    }    // Public function to perform in-order traversal of the BST    void inOrder() {        inOrderTraversal(root);        cout << endl;    }    // Public function to search for a key in the BST    bool search(int key) {        return searchBST(root, key) != nullptr;    } }; int main() {    BST bst;    // Insert nodes into the binary search tree    bst.insert(5);    bst.insert(3);    bst.insert(8);    bst.insert(2);    bst.insert(4);    bst.insert(7);    bst.insert(9);    // Perform an in-order traversal to see the sorted BST    cout << "In-order Traversal of BST: ";    bst.inOrder();    // Search for a key in the BST    int key = 4;    if (bst.search(key))        cout << "Key " << key << " found in the BST." << endl;    else        cout << "Key " << key << " not found in the BST." << endl;    return 0; }

Output:

mathematicaCopy code

In-order Traversal of BST: 2 3 4 5 7 8 9 Key 4 found in the BST.

In this code, the BST class contains functions for inserting, performing in-order traversal, and searching in the BST. The BST is created and manipulated using the public functions of the class.