.. include:: ../global.rst

.. index::
    pair: C++; Binary Search Trees

Binary Search Trees
==========================

.. _binarySearchTrees:

- Binary search trees use the concepts underpinning the binary search algorithm to create a dynamic data structure. The key word here is dynamic. Unlike sorted arrays, binary search trees support the efficient addition and removal of elements in addition to searches, making them the perfect blend of the algorithmic efficiency of binary search and the adaptability of dynamic data structures. They also make for wonderful decorative mobiles for any room.

.. image:: tree.png
    :scale: 25%

- This is what one looks like. Isn't it cool? Also I can add images now it's really easy lowkey.
- Nodes are a good example of a search tree, cuz they're like, data that connects to more data.
- It's a lot like using a system like linux where everything is all connected to your root or whatever
- We search a binary search tree by walking down from the root node. At each step, we determine whether to explore the left or right subtree by comparing the value at the current node with the target value.
- Basically, exploring a node tree is a binary search but it can branch out and have a bit more depth to itself
- Really good if your data can be used for multiple things, and it's all interconnected. An array can still work for simpler things though. It's like my mom always said, KISS: Keep It Simple, Stupid.

.. code-block:: cpp
    
    #include <iostream>
    using namespace std;

    // Define a node in the Binary Search Tree
    struct Node {
    int data;          // Value stored in the node
    Node* left;        // Pointer to the left child
    Node* right;       // Pointer to the right child

    // Constructor to initialize the node
    Node(int value) {
    data = value;
    left = right = nullptr;
    }
    };

    // Class for Binary Search Tree operations
    class BST {
    private:
    Node* root;

    // Helper function for insertion (recursive)
    Node* insert(Node* node, int value) {
    if (node == nullptr) {
    // Create a new node if reached a null spot
    return new Node(value);
    }

    if (value < node->data) {
    // Insert in the left subtree
    node->left = insert(node->left, value);
    } else if (value > node->data) {
    // Insert in the right subtree
    node->right = insert(node->right, value);
    }
    // If value == node->data, do nothing (no duplicates)

    return node;
    }

    // Helper function to search a value in the tree
    bool search(Node* node, int value) {
    if (node == nullptr) {
    return false; // Value not found
    }

    if (value == node->data) {
    return true; // Value found
    } else if (value < node->data) {
    return search(node->left, value); // Search left
    } else {
    return search(node->right, value); // Search right
    }
    }

    // Helper function for in-order traversal
    void inOrderTraversal(Node* node) {
    if (node == nullptr) return;

    inOrderTraversal(node->left);       // Visit left subtree
    cout << node->data << " ";          // Visit current node
    inOrderTraversal(node->right);      // Visit right subtree
    }

    public:
    // Constructor to initialize BST
    BST() {
    root = nullptr;
    }

    // Public insert function
    void insert(int value) {
    root = insert(root, value);
    }

    // Public search function
    bool search(int value) {
    return search(root, value);
    }

    // Public in-order traversal function
    void displayInOrder() {
    cout << "In-order traversal: ";
    inOrderTraversal(root);
    cout << endl;
    }
    };

    // Main function to demonstrate BST operations
    int main() {
    BST tree;

    // Insert values
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);

    // Display the tree (in-order should print sorted values)
    tree.displayInOrder();

    // Search for some values
    int key = 40;
    if (tree.search(key)) {
    cout << "Found " << key << " in the tree.\n";
    } else {
    cout << key << " not found in the tree.\n";
    }

    key = 90;
    if (tree.search(key)) {
    cout << "Found " << key << " in the tree.\n";
    } else {
    cout << key << " not found in the tree.\n";
    }

    return 0;
    }