A binary Search Tree is a classification of Trees in which every node in the tree can have at most two children, the left child, and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

The properties that separate a binary search tree from a regular binary tree:

**Order Property**: In a BST, for each node, the left subtree contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key. This is not required for a regular binary tree.**No Duplicate Keys**: Typically, BSTs do not allow duplicate keys. Each key must be unique and placed in a specific order as per the BST property. A regular binary tree can have duplicate keys.**Efficient Search Operations**: Due to the ordered nature of a BST, search operations (as well as insertions and deletions) can be performed more efficiently, often in O(log n) time for balanced trees. Regular binary trees do not have this order, making search operations potentially less efficient, with a time complexity of O(n) in the worst case.

Lets us see an example of a binary search tree.

In this BST, we can observe that the left child of every node has a value less than its parent node, and the right child of every node has a value greater than its parent node.

**Search Operation in Binary Search Tree**

The search operation in a BST takes advantage of the tree's ordered structure. Starting at the root, the algorithm compares the target value to the current node's value. If they match, the search is successful. If the target is less than the current node's value, the algorithm recurses into the left subtree; if greater, it recurses into the right subtree. This process continues until the target is found or a leaf node is reached, indicating that the target is not in the tree.

### Algorithm

- Start at the root node.
- If the root is None, the target is not in the tree.
- Compare the target value with the value of the current node:
- If equal, the target is found.
- If less, move to the left child and repeat the process.
- If greater, move to the right child and repeat the process.

- If a leaf node is reached and the target is not found, the target is not in the tree.

Consider the following BST:

```
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
```

To search for the value 7:

- Start at the root (8): 7 is less than 8, so move to the left child (3).
- At node 3: 7 is greater than 3, so move to the right child (6).
- At node 6: 7 is greater than 6, so move to the right child (7).
- At node 7: 7 is equal to 7, so the target is found.

### Implementation

**Output**

`Value 7 found in the BST.`

This code defines a TreeNode class and two functions: search_bst for searching a value in a BST, and insert for inserting new values into the BST. The example usage demonstrates creating a BST and searching for a value within it.

Now let us understand the procedure to insert and delete a node into the Binary Search Tree.

## Inserting a node into Binary Search Tree

Consider a Binary Search Tree â€˜Tâ€™ and an arbitrary node â€˜Nâ€™ having value stored as â€˜Valâ€™. Below is the procedure to insert the node â€˜Nâ€™ into â€˜Tâ€™.

- First, we will compare the value â€˜Valâ€™ with the data stored in the root node.
- If â€˜Valâ€™ is greater than the root node's value, we will move to its right subtree.
- If â€˜Valâ€™ is smaller than the root node's value, we will move to its left subtree.
- We will repeat the first to third step until the current root node does not have left and right subtree.
- Now, if â€˜Valâ€™ is smaller than the value of the current root node, we will insert node â€˜Nâ€™ as its left child.
- Else if â€˜Valâ€™ is greater than the value of the current root node, we will insert node â€˜Nâ€™ as its right child.

Now let us try inserting a node with â€˜Valâ€™ equal to 5 into the above tree.

Comparing the value â€˜5â€™ from the value of the root and finding it to be greater, so moving to the right subtree.

Comparing the value â€˜5â€™ from the value of the current root and finding it to be smaller, so moving to the left subtree.

Comparing the value â€˜5â€™ from the value of the current root and finding it to be greater, so moving to the right subtree.

On finding the current root without any subtree, we will insert the node â€˜Nâ€™ as the right child.