Binary Search Trees

Binary search trees have the property that the node to the left contains a smaller value than the node pointing to it and the node to the right contains a larger value than the node pointing to it.

It is not necessary that a node in a 'Binary Search Tree' point to the nodes whose value immediately precede and follow it.

Example: The tree shown in fig is a binary search tree.

Inserting into a Binary Search Tree: Consider a binary tree T. Suppose we have given an ITEM of information to insert in T. The ITEM is inserted as a leaf in the tree. The following steps explain a procedure to insert an ITEM in the binary search tree T.

1. Compare the ITEM with the root node.
2. If ITEM>ROOT NODE, proceed to the right child, and it becomes a root node for the right subtree.
3. If ITEM<ROOT NODE, proceed to the left child.
4. Repeat the above steps until we meet a node which has no left and right subtree.
5. Now if the ITEM is greater than the node, then the ITEM is inserted as the right child, and if the ITEM is less than the node, then the ITEM is inserted as the left child.

Example: Show the binary search tree after inserting 3, 1,4,6,9,2,5,7 into an initially empty binary search tree.

Solution: The insertion of the above nodes in the empty binary search tree is shown in fig:

Deletion in a Binary Search Tree: Consider a binary tree T. Suppose we want to delete a given ITEM from binary search tree. To delete an ITEM from a binary search tree we have three cases, depending upon the number of children of the deleted node.

1. Deleted Node has no children: Deleting a node which has no children is very simple, as replace the node with null.
2. Deleted Node has Only one child: Replace the value of a deleted node with the only child.
3. Deletion node has only two children: In this case, replace the deleted node with the node that is closest in the value to the deleted node. To find the nearest value, we move once to the left and then to the right as far as possible. This node is called the immediate predecessor. Now replace the value of the deleted node with the immediate predecessor and then delete the replaced node by using case1 or case2.

Example: Show that the binary tree shown in fig (viii) after deleting the root node.

Solution: To delete the root node, first replace the root node with the closest elements of the root. For this, first, move one step left and then to the right as far as possible to the node.Then delete the replaced node. The tree after deletion shown in fig: