# Binary Search Trees (BST)

A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:
1.  The left subtree of a node contains only nodes with keys **less than** the node's key.
2.  The right subtree of a node contains only nodes with keys **greater than** the node's key.
3.  The left and right subtrees must also be binary search trees.

## 1. The Core Concept

This structure allows for fast lookup, addition, and removal of items. It works like a sorted list but with faster insertion/deletion.

*   **Root:** The top node.
*   **Leaf:** A node with no children.

## 2. Operations & Complexity

| Operation | Average Case | Worst Case |
| :--- | :--- | :--- |
| **Search** | $O(\log n)$ | $O(n)$ |
| **Insert** | $O(\log n)$ | $O(n)$ |
| **Delete** | $O(\log n)$ | $O(n)$ |

*   **Average Case:** Occurs when the tree is balanced (height is $\log n$).
*   **Worst Case:** Occurs when the tree is skewed (essentially a linked list), e.g., inserting 1, 2, 3, 4, 5 in order.

## 3. Tree Traversal

Traversal is the process of visiting all the nodes in the tree.

### In-Order (Left, Root, Right)
Visits nodes in ascending sorted order.
*   `Left -> Root -> Right`

### Pre-Order (Root, Left, Right)
Useful for creating a copy of the tree.
*   `Root -> Left -> Right`

### Post-Order (Left, Right, Root)
Useful for deleting the tree (delete children before parent).
*   `Left -> Right -> Root`

## 4. Implementation (Python)

```python
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

def search(root, key):
    if root is None or root.val == key:
        return root
    
    if root.val < key:
        return search(root.right, key)
    
    return search(root.left, key)
```

## 5. Balanced BSTs

To avoid the $O(n)$ worst-case scenario, we use **Self-Balancing Binary Search Trees**. These trees automatically keep their height small (logarithmic) after insertions and deletions.

*   **AVL Trees:** Strictly balanced.
*   **Red-Black Trees:** Loosely balanced (faster insertion/deletion than AVL).

## 6. Tree Rotations

Tree rotations are operations that change the structure of a binary search tree without affecting the order of the elements. They are used to rebalance trees (like AVL or Red-Black trees).

*   **Left Rotation:** Moves a node down to the left and its right child up.
*   **Right Rotation:** Moves a node down to the right and its left child up.

Rotations are $O(1)$ operations because they only involve changing a few pointers.

[[programming/algorithms]]
[[programming/graph-theory-basics]]
[[programming/arrays-vs-linked-lists]]