.. _binary-search-tree:

Binary Search Tree (BST)
============
A Binary Search Tree is a special type of binary tree where the value stored in node **u** is greater than or equal to all values in its left child's subtree, and greater than or equal to all values in its right child's subtree.  
A BST allows us to add, delete, or search for a value more efficiently.  
Searching, insertion, and deletion form the fundamental operations of a BST.

.. code-block:: python
   :linenos:

   class Node:
       def __init__(self, key):
           self.left = None    # Bache chap
           self.right = None   # Bache rast
           self.val = key      # Meghdar

Search
------
The search operation for a value x proceeds as follows:

- First, we examine the value at the root. If it is greater than x, we recursively repeat this step on the left subtree. If smaller, we proceed with the right subtree.

- We continue this until either the target child subtree does not exist for further traversal, or the examined node's value equals x.

Insertion
---------
The insertion operation for a value x proceeds as follows:

- First, we examine the root's value. If it is greater than or equal to x, we recursively repeat this step on the left subtree. If smaller, we proceed with the right subtree.

- We continue until the target child subtree does not exist, then add a new child node with value x in that position.

Deletion
--------
After locating the target node using search, three cases may occur:

1. **Leaf node (no children)**: Immediate deletion.
2. **Single child**: Replace the node with its child.
3. **Two children**: Two deletion methods exist. Let **u** be the node to delete.

**Method 1** (Successor replacement):
1. Find node **v** - the smallest value in u's right subtree.
2. Replace u's value with v's value.
3. Delete v (which can only have 0 or 1 children, as v is the minimum).

**Method 2** (Predecessor replacement):
- Similar to Method 1, but using the largest value in u's left subtree.