What is Binary Search Tree and write operations are performed on a binary search tree.

 

BINARY SEARCH TREES:

•     In a binary tree, every node can have a maximum of two children but there is no order of nodes based on their values.
•     In a binary tree, the elements are arranged as they arrive in the tree, from top to bottom and left to right. To enhance the performance of a binary tree, we use a special type of binary tree known as the binary Search Tree.
•      The binary search tree mainly focuses on the search operation in a binary tree.
•      Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only larger values in its right subtree.

 

Example

The following tree is a binary search tree. In this tree, a left subtree of every node contains nodes with smaller values and the right subtree of every node contains larger values.

The following operations are performed on a binary search tree:-

1)     Search

2)     Insertion

3)     Deletion

Search Operation in BST

 

In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation is performed as follows:-

Step 1: Read the search element from the user

Step 2: Compare, the search element with the value of the root node in the tree.

Step 3: If both are matching, then display "Given node found!!!" and terminate the function

Step 4: If both are not matching, then check whether the search element is smaller or larger than that node value.

Step 5: If the search element is smaller, then continue the search process in the left subtree.

Step 6: If the search element is larger, then continue the search process in the right subtree.

Step 7: Repeat the same until we found an exact element or we completed with a leaf node

Step 8: If we reach the node with search value, then display "Element is found" and terminate the function.

Step 9: If we reach a leaf node and it is also not matching, then display "Element not found" and terminate the function.

 

Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n) time complexity. In a binary search tree, a new node is always inserted as a leaf node. The insertion operation is performed as follows:-

Step 1: Create a new node with the given value and set its left and right to NULL.

Step 2: Check whether the tree is Empty.

Step 3: If the tree is Empty, then set root to the new node.

Step 4: If the tree is Not Empty, then check whether the value of a new node is smaller or larger than the node (here it is the root node).

Step 5: If newNode is smaller than or equal to the node, then move to its left child. If the new node is larger than the node, then move to its right child.

Step 6: Repeat the above step until we reach a leaf node (e.i., reach to NULL).

Step 7: After reaching a leaf node, then insert the new node as a left child if the new node is smaller or equal to that leaf else insert it as the right child.

 

Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O (log n) time complexity. Deleting a node from a binary search tree has the following three cases:-

 

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST:-

Step 1: Find the node to be deleted using the search operation

Step 2: Delete the node using a free function (If it is a leaf) and terminate the function.

 

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST:-

Step 1: Find the node to be deleted using the search operation

Step 2: If it has only one child, then create a link between its parent and child nodes.

Step 3: Delete the node using a free function and terminate the function.

 

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST:-

Step 1: Find the node to be deleted using the search operation

Step 2: If it has two children, then find the largest node in its left subtree (OR) the smallest node in its right subtree.

Step 3: Swap both deleting node and node which found in the above step.

Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2

Step 5: If it comes to case 1, then delete using case 1 logic.

Step 6: If it comes to case 2, then delete using case 2 logic.

Step 7: Repeat the same process until the node is deleted from the tree.