Binary Search Tree

Definition:

A Binary Search Tree (BST) is a type of binary tree in which the nodes are arranged in a specific order.

Also known as an ordered binary tree, a BST maintains a specific ordering property that facilitates efficient search, insertion, and deletion operations.

Ordering Property:

In a Binary Search Tree:

• The value of all nodes in the left sub-tree is less than the value of the root node.
• The value of all nodes in the right subtree is greater than or equal to the value of the root node.
• This ordering property ensures that the elements in the tree are organized in such a way that searching for a specific value can be done efficiently.

Recursive Application:

• The ordering property of a BST is recursively applied to all the left and right subtrees of each node in the tree.
• Each subtree of a BST is also a BST itself, adhering to the same ordering property.

Example:

Advantages of using binary search tree

• Searching becomes very efficient in a binary search tree since we get a hint at each step, about which sub-tree contains the desired element.
• The binary search tree is considered as an efficient data structure in compare to arrays and linked lists. In the searching process, it removes half a sub-tree at every step. Searching for an element in a binary search tree takes o(log2n) time. In the worst case, the time it takes to search an element is 0(n).
• It also speeds up the insertion and deletion operations as compared to that in array and linked list.

Q. Create the binary search tree using the following data elements.

43, 10, 79, 90, 12, 54, 11, 9, 50

Operations on Binary Search Tree

SEARCH OPERATION

1. Compare:

• Start with the root node of the BST.
• Compare the key you are searching for with the value of the root node.

2. Match Found:

• If the key matches the value of the root node, return the location of the node (root).

3.Move Left or Right:

• If the key is less than the value of the root node, move to the left subtree.
• If the key is greater than the value of the root node, move to the right subtree.

4.Repeat Recursively:

• Repeat steps 2 and 3 recursively until a match is found or until you reach a leaf node (a node with no children).

5.Match Not Found:

• If the key is not found after traversing the entire tree, return NULL or indicate that the key was not found.

Search item=50 in the above Binary search tree(BST)

Searching is done as below:

Algorithm for search operation in Binary Search Tree

Search (ROOT, ITEM)

Step 1: IF ROOT -> DATA = ITEM OR ROOT = NULL
    Return ROOT
   ELSE
   IF ITEM < ROOT -> DATA
   Return search(ROOT -> LEFT, ITEM)
  ELSE
   Return search(ROOT -> RIGHT,ITEM)
  [END OF IF]
  [END OF IF]
Step 2: END

Insertion operation in Binary 

Insert function is used to add a new element in a binary search tree at appropriate location. Insert function is to be designed in such a way that it must  not violate the property of the binary search tree at each value.

• Allocate the memory for a tree.
• Set the data part to the value and set the left and right pointer of the tree, pointing to NULL.
• If the item to be inserted, will be the first element of the tree, then the left and right of this node will point to NULL.
• Else, check if the item is less than the root element of the tree, if this is true, then recursively perform this operation with the left of the root.
• If this is false, then perform this operation recursively with the right subtree of the root.

Insert 35 into the given BST

Algorithm for Insert Operation in BST

Insert (TREE, ITEM)
Step 1: IF TREE = NULL
  Allocate memory for TREE
  SET TREE -> DATA = ITEM
  SET TREE -> LEFT = TREE -> RIGHT = NULL
  ELSE
   IF ITEM < TREE -> DATA
    Insert(TREE -> LEFT, ITEM)
  ELSE
   Insert(TREE -> RIGHT, ITEM)
  [END OF IF]
  [END OF IF]
Step 2: END

Deletion

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 in such a way, that the property of the binary search tree doesn't violate. There are three situations of deleting a node from a binary search tree.

The node to be deleted is a leaf node

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

We will be deleting value=35 from the given binary search Tree:

The node to be deleted has only one child.

In this case, replace the node with its child and delete the child node, which now contains the value which is to be deleted. Simply replace it with the NULL and free the allocated space.

Let us delete 10 from the given tree:

The node to be deleted has two children.

It is a bit complex compared to the other two cases. However, the node which is to be deleted, is replaced with its in-order successor or predecessor recursively until the node value (to be deleted) is placed on the leaf of the tree. After the procedure, replace the node with NULL and free the allocated space.

Algorithm for delete operation in Binary Search Tree

Delete (TREE, ITEM)

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]