Binary Search Trees(BST)

 Binary Search Trees (BST):

A binary search tree, also known as an ordered binary tree. In a binary search tree, all the nodes in the left sub-tree have a value less than that of the root node. Correspondingly, all the nodes in the right sub-tree have a value either equal to or greater than the root node. The same rule is applicable to every sub-tree in the tree.

In the above figure, we can observe that the root node is 40, and all the nodes of the left subtree are smaller than the root node, and all the nodes of the right subtree are greater than the root node.

Similarly, we can see the left child of root node is greater than its left child and smaller than its right child. So, it also satisfies the property of binary search tree. Therefore, we can say that the tree in the above image is a binary search tree.

In the above tree, the value of root node is 40, which is greater than its left child 30 but smaller than right child of 30, i.e., 55. So, the above tree does not satisfy the property of Binary search tree. Therefore, the above tree is not a binary search tree.

Example of creating a binary search tree

Example : State whether the binary trees in below Fig. are binary search trees or not.

Example : Now, let's see the creation of binary search tree using an example.

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

• First, we have to insert 45 into the tree as the root of the tree.
• Then, read the next element; if it is smaller than the root node, insert it as the root of the left subtree, and move to the next element.
• Otherwise, if the element is larger than the root node, then insert it as the root of the right subtree.

Now, let's see the process of creating the Binary search tree using the given data element. The process of creating the BST is shown below 

Example : Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81

OPERATIONS ON BINARY SEARCH TREES

Searching for a Node in a Binary Search Tree:

The search function is used to find whether a given value is present in the tree or not. The searching process begins at the root node. 

The function first checks if the binary search tree is empty. If it is empty, then the value we are searching for is not present in the tree. So, the search algorithm terminates by displaying an appropriate message. 

However, if there are nodes in the tree, then the search function checks to see if the key value of the current node is equal to the value to be searched.

If not, it checks if the value to be searched for is less than the value of the current node, in which case it should be recursively called on the left child node. 

In case the value is greater than the value of the current node, it should be recursively called on the right child node.

See the illustration below for a better understanding:

Algorithm to search for a given value in a binary search tree

Insert a value in a Binary Search Tree:

A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. The below steps are followed while we try to insert a node into a binary search tree:

 

v  Initilize the current node (say, currNode or node) with root node

v  Compare the key with the current node.

v  Move left if the key is less than or equal to the current node value.

v  Move right if the key is greater than current node value.

v  Repeat steps 2 and 3 until you reach a leaf node.

v  Attach the new key as a left or right child based on the comparison with the leaf node’s value.

Follow the below illustration for a better understanding:

Algorithm to insert a given value in a binary search tree

Deleting a Node from a Binary Search Tree:

Delete function is used to delete the specified node from a binary search tree. However, we must delete a node from a binary search tree so that the property of the binary search tree doesn't violate. There are three situations in which a node can be deleted from a binary search tree.

Case 1: Deleting a Node that has No Children

It is the simplest case, in this case, replace the leaf node with the NULL and simple free the allocated space.

In the following image, we are deleting the node 85, since the node is a leaf node, therefore the node will be replaced with NULL and allocated space will be freed.

Case 2: Deleting a Node with One Child

In this case, the node’s child is set as the child of the node’s parent (i.e replace the node with its child).

if the node is the left child of its parent, the node’s child becomes the left child of the node’s parent. Correspondingly, if the node is the right child of its parent, the node’s child becomes the right child of the node’s parent.

In the following image, the node 12 is to be deleted. It has only one child. The node will be replaced with its child node and the replaced node 12 (which is now leaf node) will simply be deleted.

Case 3: Deleting a Node with Two Children

this case, replace the node’s value with its in-order predecessor (largest value in the left sub-tree) or in-order successor (smallest value in the right sub-tree).

Deleting node 56 from the given binary search tree  by replacing node 56 with its in-order predecessor

This deletion could also be handled by replacing node 56 with its in-order successor

ex: In the following image, the node 50 is to be deleted which is the root node of the tree. 

The in-order traversal of the tree given below 6, 25, 30, 50, 52, 60, 70, 75.

replace 50 with its in-order successor 52. Now, 50 will be moved to the leaf of the tree, which will simply be deleted.

Delete (TREE, ITEM)

o         Step 1: IF TREE = NULL

   Write "item not found in the tree" ELSE IF ITEM < TREE -> DATA

  Delete(TREE->LEFT, ITEM)

  ELSE IF ITEM > TREE -> DATA

   Delete(TREE -> RIGHT, ITEM)

  ELSE IF TREE -> LEFT AND TREE -> RIGHT

  SET TEMP = findLargestNode(TREE -> LEFT)

  SET TREE -> DATA = TEMP -> DATA

   Delete(TREE -> LEFT, TEMP -> DATA)

                 ELSE

   SET TEMP = TREE

   IF TREE -> LEFT = NULL AND TREE -> RIGHT = NULL

   SET TREE = NULL

  ELSE IF TREE -> LEFT != NULL

  SET TREE = TREE -> LEFT

  ELSE

    SET TREE = TREE -> RIGHT

  [END OF IF]

  FREE TEMP

[END OF IF]

o             Step 2: END