1.2) Binary Search Tree Implementation

A Binary Search Tree (BST) is a type of data structure that allows efficient storage and retrieval of elements while maintaining a specific order.

In a BST, each node has at most two children: a left child and a right child. The key property of a BST is that for each node, all elements in its left subtree are smaller, and all elements in its right subtree are larger.

Binary Search Tree Implementation:

Here’s a simple implementation of a Binary Search Tree in C++:

#include <iostream>
using namespace std;

class TreeNode {
public:
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

class BST {
private:
    TreeNode* root;

    TreeNode* insertRecursive(TreeNode* root, int val) {
        if (root == nullptr) {
            return new TreeNode(val);
        }

        if (val < root->data) {
            root->left = insertRecursive(root->left, val);
        } else {
            root->right = insertRecursive(root->right, val);
        }

        return root;
    }

public:
    BST() {
        root = nullptr;
    }

    void insert(int val) {
        root = insertRecursive(root, val);
    }
};

int main() {
    BST bst;

    bst.insert(15);
    bst.insert(8);
    bst.insert(20);
    bst.insert(12);
    bst.insert(25);

    return 0;
}

BST Code Explanation:

1. TreeNode class represents a single node in the Binary Search Tree. It has data, a pointer to the left child, and a pointer to the right child.
2. In the TreeNode constructor, the data is set, and both left and right pointers are initialized to nullptr.
3. BST class represents the Binary Search Tree itself. It has a private member root, which points to the root node of the tree.
4. The private member function insertRecursive is a helper function that inserts a new node with value val into the tree rooted at root. It uses a recursive approach: if the current node is nullptr, it creates a new node with the given value. Otherwise, it decides whether to insert the value in the left or right subtree based on the comparison with the current node’s data.
5. The public member function insert serves as a wrapper for inserting elements into the tree. It calls the insertRecursive function with the root node and the value to be inserted.
6. In the main function, a BST object bst is created.
7. Elements (15, 8, 20, 12, and 25) are inserted into the BST using the insert function.

This code creates a simple Binary Search Tree and inserts elements into it while maintaining the BST property: elements in the left subtree are smaller, and elements in the right subtree are larger. This structure allows for efficient searching, insertion, and deletion of elements in the tree.

Time Complexity:

1. Insertion: When inserting an element into the BST, the time complexity depends on the height of the tree. In the best case, where the tree is well-balanced, the height is O(log N), where N is the number of nodes in the tree. However, in the worst case, where the tree is skewed (all elements are inserted in one direction), the height can become O(N), resembling a linked list. This is unlikely to happen with a well-balanced insertion sequence or with random data.
2. Search: Searching for an element in a balanced BST takes O(log N) time on average, due to the binary search property. In the worst case (skewed tree), the time complexity is O(N), similar to the worst case for insertion.

Space Complexity:

1. The space complexity of the TreeNode class is O(1) since it only stores a few integer variables and pointers for left and right children, regardless of the number of nodes.
2. The space complexity of the BST class mainly depends on the number of nodes in the tree. If you have N nodes in the tree, the space complexity for storing the tree would be O(N).

In summary:

• Insertion Time Complexity: Best Case: O(log N), Worst Case: O(N)
• Search Time Complexity: Best Case: O(log N), Worst Case: O(N)
• Space Complexity: O(N) (due to storing N nodes in the tree)