.. include:: global.rst

===========================
5-Binary Search Trees (BSTs)
===========================

    Binary search trees use the concepts underpinning the binary search
    algorithm to create a dynamic data structure. This makes them
    a blend of the efficiency of binary search with the adaptability of
    dynamic data structures.

-------------------------------
Binary Search Tree Structure
-----------------------------

    Trees are hierarchical data structures composed of branching nodes.
    Each tree node may have two child pointers, forming a binary structure.

    A node contains a value and up to two child pointers:

    .. code-block:: none

        TreeNode {
        Type: value
        TreeNode: left
        TreeNode: right
        TreeNode: parent
        }

    Nodes with at least one child are called **internal nodes**.
    Nodes with no children are **leaf nodes**.

    A binary search tree (BST) starts at a single **root node** and branches
    downward. Programs access the BST through a single pointer to the root.

-------------------------------------
    The Binary Search Tree Property
--------------------------------------

    For any node ``N``:

    - All values in the left subtree of ``N`` are **less than** ``N.value``.
    - All values in the right subtree of ``N`` are **greater than** ``N.value``.

    This ordering effectively keeps the tree sorted.

    By default, BSTs assume **unique values**. Handling duplicates requires
    modifying the property.

--------------------------
    Searching a BST
--------------------------

    Searching begins at the root. At each node:

    - If ``target < node.value`` → go left
    - If ``target > node.value`` → go right
    - If ``target == node.value`` → success

    Recursive search pseudocode:

    .. code-block:: none

        FindValue(TreeNode: current, Type: target):
            IF current == null:
                return null
            IF current.value == target:
                return current
            IF target < current.value AND current.left != null:
                return FindValue(current.left, target)
            IF target > current.value AND current.right != null:
                return FindValue(current.right, target)
            return null

    Iterative version:

    .. code-block:: none

        FindValueItr(TreeNode: root, Type: target):
            TreeNode: current = root
            WHILE current != null AND current.value != target:
                IF target < current.value:
                    current = current.left
                ELSE:
                    current = current.right
            return current

    Complexity is proportional to the **depth of the target value**.

----------------------------------
    Searching Trees vs. Arrays
---------------------------------

    - **Sorted arrays**: binary search gives logarithmic lookup, but insertions and deletions are expensive.
    - **Binary search trees**: slightly more overhead, but dynamic updates are efficient.

    Thus, BSTs shine in **dynamic environments** where data changes frequently.

--------------------------
    Adding Nodes
--------------------------

    Insertion follows the same path as search until a dead end is reached:

    .. code-block:: none

        InsertTreeNode(BinarySearchTree: tree, Type: new_value):
            IF tree.root == null:
                tree.root = TreeNode(new_value)
            ELSE:
                InsertNode(tree.root, new_value)

        InsertNode(TreeNode: current, Type: new_value):
            IF new_value == current.value:
                Update node as needed
                return
            IF new_value < current.value:
                IF current.left != null:
                    InsertNode(current.left, new_value)
                ELSE:
                    current.left = TreeNode(new_value)
                    current.left.parent = current
            ELSE:
                IF current.right != null:
                    InsertNode(current.right, new_value)
                ELSE:
                    current.right = TreeNode(new_value)
                    current.right.parent = current

    Complexity: proportional to the depth of the insertion path.

--------------------------
    Removing Nodes
--------------------------

    Three cases exist:

    1. **Leaf node** – Delete directly and update parent.
    2. **Node with one child** – Promote the child to take its place.
    3. **Node with two children** – Replace node with its **successor**

    (the leftmost node in the right subtree).

    .. code-block:: none

        RemoveTreeNode(BinarySearchTree: tree, TreeNode: node):
            IF tree.root == null OR node == null:
                return

            # Case A: Leaf node
            IF node.left == null AND node.right == null:

            # Case B: One child
            IF node.left == null OR node.right == null:

            # Case C: Two children
            successor = node.right
            WHILE successor.left != null:
            successor = successor.left
            RemoveTreeNode(tree, successor)

    Complexity: proportional to tree depth.

-----------------------------------
    Balanced vs. Unbalanced Trees
-----------------------------------

    - **Balanced BSTs**: operations scale as ``O(log N)``.
    - **Unbalanced BSTs**: can degrade to ``O(N)``, resembling a linked list.

    Balanced trees (like AVL or Red-Black trees) solve this problem by enforcing
    balance rules.


.. literalinclude:: binary_trees.cpp
   :language: cpp 

.. literalinclude:: binary_trees.py
   :language: python