Binary Search Trees

Binary search trees are special type of binary trees in which elements are inserted in a prescribed order. A binary search tree is a binary tree which is either empty or in which the following conditions are satisfied:

1. All the elements of the left subtree of the root are less than the element of the root
2. All the elements of the right subtree of the root are greater than the element of the root
3. The left and right subtrees of a binary search tree are binary search trees once again

So the definition of a binary search tree is again recursive. An example of a binary search tree is as shown in figure-1

It must be emphasized that no two nodes in a binary search tree can hold equal data value. The operation defined on a binary search tree are typically based on this property. A binary search tree has following basic operations: search, insert and delete.

Searching in a Binary Search Tree

It is very easy to search for a data item in a binary search tree. In the item to be searched is compared to the data item of the root. If it is equal then the search terminates and the control is returned back. If the item is less than the data item of the root then we search in the left subtree; otherwise we search in the right subtree. And this process is called recursively until the desired item is not found or entire tree gets exhausted.

For this we will assume the previous definition of a tree node, that is TNode.

Here is the function that searched for a given item in a binary search tree.

search(TNode *rt, int item)

{
if (rt == NULL)
return 0;
else if (rt->data == item)
return 1;
else if (rt->data > item)
search(rt->lchild, item);
else
search(rt->rchild, item);
}

Here the function search() returns a value 1 if it finds the data item otherwise it returns a value 0.

Insertion into a Binary Search Tree

While inserting a data item into a binary search tree one must remember the conditions mentioned in the definition of a binary tree so that the tree remains a binary search tree after insertion. In this if the tree is empty then the item to be inserted is placed at the position specified by root node rt. If the item is greater than the data item of the root node than we call the function itself with its right subtree as its root node. And if the data item is less than the data item of the root node then we call the function itself with its right subtree as its root node. And this process continues until we find root node as an empty.

Here is the function that implements this task.

Tree_Insert(TNode **rt, int item)

{
if (*rt == NULL)
{
(*rt) = getnode();
(*rt)->data = item;
(*rt)->lchild = NULL;
(*rt)->rchild = NULL;
}
else if (((*rt)->data)>item)
Tree_Insert(&((*rt)->lchild), item);
else if (((*rt)->data)
Tree_Insert(&((*rt)->rchild), item);
else
{
printf("\nIllegal data item.");
return;
}
}

Deletion from a Binary Search Tree

When we delete a node from a binary search tree then there are two possibility whether the tree is empty or not. If the tree is empty then it will just display an error message and the control is returned back. If the tree is not empty then the item is searched. Again there are two possibilities – whether the item is in the tree or not. The item is searched by using the search() functions. the search function searches not only the node containing the data item but also its parent node.

If the item is found then again there are four possibilities:

1. The deleted node has no children
2. The deleted node has both left and right children
3. The deleted node has only left child
4. The deleted node has only right child

So out delete function must include all these possibilities.

Tree_Delete(TNode **rt, int item)

{
TNode *parent, *suc, *loc;
if (*rt == NULL)
{
printf("\nTree is empty. Press any key to continue....");
getch();
return;
}
search(rt, item, &parent, &loc);
if (loc == NULL)
{
printf("\nItem not found");
return;
}
if ((loc->lchild != NULL)&&(loc->rchild != NULL))
{
parent = loc;
suc = loc->rchild;
while (suc->lchild != NULL)
{
parent = suc;
suc = suc->lchild;
}
loc->data = suc->data;
loc = suc;
}
if (loc->lchild == NULL)
{
if (parent != NULL)
{
if (parent->lchild == loc)
parent->lchild = loc->rchild;
else
parent->rchild = loc->rchild;
}
else
(*rt) = loc->rchild;
}
if (loc->rchild == NULL)
{
if (parent != NULL)
{
if (parent->lchild == loc)
parent->lchild = loc->lchild;
else
parent->rchild = loc->lchild;
}
else
(*rt) = loc->lchild;
}
free(loc);
}

Now we will write the definition of search() function that will find the location of the node to be deleted, if it is present, along with its parent node.

search(TNode **rt, int item, TNode **p, TNode **loc)

{
(*p) = NULL;
(*loc) = (*rt);
 
while ((*loc != NULL)&&(((*loc)->data) != item))
{
(*p) = (*loc);
if ((*loc)->data > item)
(*loc) = (*loc)->lchild;
else
(*loc) = (*loc)->rchild;
}

Reconstruction of a Binary Tree Using Inorder and Preorder Traversals

In practical situations there are possibilities that inorder or preorder or postorder traversals of two or more trees can produce the same sequence of nodes. Consider the two binary trees as shown in figure-12.40. Inorder traversal of these two binary trees may result in the same sequence of nodes, that is DBEAC.

Figure 2

Similarly preorder or postorder traversals of different binary trees can produce the same sequence of nodes. As a result it is not possible to reconstruct a tree if its inorder or preorder or postorder is provided alone. But if inorder and preorder traversals are provided then it is possible to reconstruct a unique binary tree. But remember that a binary tree can not be uniquely reconstructed if its preorder and postorder traversals are provided.

Now let us see how to reconstruct a binary tree if inorder and preorder traversals are provided. Let we have following sequence of nodes:

Inorder Sequence: D  B  H  E  I  A  C  J  G

Preorder Sequence : A  B  D  E  H  I  C  G  J

Figure 3

We know that the preorder visits the root node first. Thus the root of the binary tree is ‘A’. We also know that the root node is visited after traversing the left subtree in inorder traversal of a binary tree. Thus the nodes which are left of the root node ‘A’ in inorder sequence belong to the left subtree and the nodes which are right of the root node ‘A’ in inorder sequence belong to the right subtree as shown in figure-3(a).

Now we will apply the same technique to both the left and right subtree once again. Let us take the left subtree. In this the preorder sequence tells that ‘B’ is the root node of this subtree. With this node ‘B’ in inorder traversal we find that the node ‘D’ is at the left side of ‘B’ and the nodes ‘H’ ‘E’ ‘I’ are at the right side of the subtree rooted ‘B’ as shown in figure-3(b). Since ‘D is the only node of the left subtree of the subtree rooted at ‘B’ so there is no problem. As far as the right subtree of the subtree rooted rooted at ‘B’ is concerned we apply the same techniques.

This process goes on until we get the complete binary tree as shown in figure-3.