What is Binary Search Tree?
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.