Reconstruction of a Binary Tree from its Inorder and Preorder Traversal

It is for you kind information that the inorder traversal of two or more different binary tree may produce the same sequence of nodes. Similarly preorder or postorder traversals may produce the same sequence of nodes. Look at all the Figure- l1 Both figures produce the same sequence of nodes if they are traversed in inorder fashion (BADCE).

Figure l1

It means that we can not reconstruct a binary tree if we are provided its inorder or preorder or postorder. However if we are provided with inorder and preorder sequence of nodes then we can construct a unique binary tree.

For example, let we have following inorder and postorder traversal of a binary tree:

Inorder Sequence:    D B G E H A C I F
Preorder Sequence :    A B D E G H C F I

We know that in preorder traversal of a binary tree, the root node is visited first. And since ‘A’ is the first node in the preorder sequence, therefore ‘A’ becomes the root node of the binary tree. And as far as the inorder traversal is concerned, the root node is visited after traversing the left sub-tree. Therefore all the nodes which are on the left side of ‘A’ in the given inorder sequence belong to the left subtree and the nodes to the right of ‘A’ belong to the right subtree of the tree as shown below:

Moreover, the order in which the nodes to the left of ‘A’ occur in the given inorder sequence is the same as the inorder sequence of the left subtree. So we can say that if there are ‘x’ number of nodes after ‘A’ in inorder sequence then the first ‘x’ nodes after ‘A’ in preorder sequence become the preorder sequence of the left subtree. This process is applied to both the left and right subtrees once again. Let we consider the left subtree. The preorder sequence of this subtree suggests that ‘B’ is the root node of this subtree. The position of ‘B’ in the inorder sequence determines the inorder sequence of the left and the right subtree as shown below:

This process continues for each subtree. Figure-l2 continues the step-by-step reconstruction of a binary tree. Here is the ‘C’ function which construct a binary tree given its inorder and preorder traversals.

Reconstruct(TreeNode *inhead, TreeNode *prehead)

/* Here inhead and prehead are pointers to the inorder list and preorder list of a binary tree */

{
 TreeNode *incurr, *precurr;
 precurr = prehead->prev->prev;
 while (precurr != prehead)
 {
 incurr = inhead->next;
 while ((incurr!=inhead)&&(incurr->data != precurr->data))
 incurr = incurr->next;
 if (incurr == inhead)
 {
 printf("\n Error in input");
 exit(0);
 }
 if (precurr->next->data == incurr->prev->data)
 {
 precurr->lchild = precurr->next;
 DelNode(incurr->prev);
 DelNode(precurr->next);
 if (precurr->next == prehead)
 precurr = precurr->prev;
 }
 else
 {
 if (precurr->next->data == incurr->next->data)
 {
 precurr->rchild = precurr->next;
 DelNode(precurr->next);
 DelNode(incurr->next);
 if (precurr->next == prehead)
 precurr = precurr->prev;
 }
 else
 precurr = precurr->prev;
 }
 }
}
DelNode(struct TreeNode *temp)
{
 temp->prev->next = temp->next;
 temp->next->prev = temp->prev;
}

Following code segment illustrates how to use this function Reconstruict()….

 ….
printf("\n Enter inorder traversal = ");
 gets(instr);
 printf("\n Enter preorder traversal = ");
 gets(prestr);
 ….
 ListCreate(&inhead,instr);
 ListCreate(&prehead,prestr);
 Reconstruct(inhead,prehead);
 TreeDisplay(prehead->next,0);
 ….

Here ListCreate() function is used to create a linked list of inorder sequence and preorder sequence of characters of a tree. And once we have such two lists we pass these two lists to Reconstruct() function in order to get a binary tree.

Figure l2

We can reconstruct a binary tree if the inorder and the postorder traversal of a binary tree is provided. But one should remember that a binary tree can not be uniquely reconstructed if its preorder and postorder traversals are provided.

Binary Search Trees

Binary trees that we have studied so far contain unordered elements. However in many applications an order data is required. For such applications, we have binary search trees. In a binary search tree data is maintained in some order. We know that the nodes in a binary tree represent some records and these records are ordered on some key properties in a binary search tree. Therefore we can define a binary search tree as:

(i)    every node has a key and no two keys have the same key value
(ii)    all keys (if any) in the left subtree are smaller than the key in the root
(iii)    all keys (if any) in the right subtree are larger than the key in the root
(iv)    the left and right subtrees of a binary search tree are binary search trees once again

We can say that the definition of a binary search tree is itself recursive. Figure-l3 shows some example of binary search trees.

Figure l3

The tree of figure-l3(e) is not a binary search tree because this tree rooted at the node ‘3’ is not a binary search tree, as its right subtree has a key value ‘2’ that is smaller than ‘3’. So it violates the third properties of the definition of a binary search tree. However all other binary trees of figure-l3 are binary search trees.

Now you can read some basic operations on binary search tree in this article.

Search in a Binary Search Tree

Since the definition of a binary search tree is recursive, therefore it is easier to describe a recursive search method. Let I want to search for an element with key ‘item’. Initially the key is compared with the key at the root. If both are equal then the search terminates successfully. If the given key is less than the key at the root then the search is initiated only at the left subtree of the current root because no element in the right subtree can have key value ‘item’. Similarly if the given key is greater than the key at the root then the search is initiated only at the right subtree of the current root because no element in the left subtree can have key value ‘item’. The search process terminates unsuccessfully when search is done on an empty tree, that is the current root node contains a NULL value.

For the sake of convenience we consider the same data type for a node as we have taken earlier, that each node has three fields – lchild, data and rchild.

Here is the algorithm which searches a given key in a binary search tree.

Algorithm: Search

Search(Root, item)

Here Root contains the address of root node and item be the element to be searched.

Step-1 : If (Root == NULL) then return 0;
Step-2 : If (Root->data == item) return 1
Else if (Root->data > item) Call Search(Root->lchild, item)
Else Call Search(Root->rchild, item)
Step-3 : Exit

Here is the ‘C’ implementation of this function:

Implementation : Search

Search(TreeNode *Root, int item)
{
 if (Root == NULL)
 return 0;
if (Root->data == item)
 return 1;
else if (Root->data > item)
 Search(Root->lchild, item);
else
 Search(Root->rchild, item);
}

This function returns 1 if search terminates successfully; otherwise returns 0. The recursion in this function can be easily converted to an iterative one since it is a tail recursion.

Here is the iterative equivalent of a Search() function.

NonRecSearch(TreeNode *Root, int item)
{
 while (Root != NULL)
 {
 if (Root->data == item)
 return 1;
 else if (Root->data > item)
 Root = Root->lchild;
 else
 Root = Root->lchild;
}
return 0;
}

The Search() function can be used in the following segment as:

….
flag = Search(Root, item);
if (flag==1)
 printf(“\nItem is searched successfully.”);
else
 printf(“\nItem is not found”);
….

Here ‘item’ contains the value to be searched.

Insertion into a Binary Search Tree

When we insert a new element into a binary search tree then there are two possibilities, either tree is empty or not. If tree is empty then we need only make root point to the new node. However if the tree is not empty then we must compare the given key with the key value in the root. If it is less then the new node must be inserted into the left subtree. If it is larger one then the new node must be inserted into the right subtree. If both keys are equal then it must display an error message because our assumption, that no two nodes have the same key, is violated. So while inserting a key into a binary search tree one must preserve the conditions mentioned in the definition of a binary search tree.

For example, let we want to insert an element with key 32 into the tree of Figure-l4(a). Here we first compare ‘32’ with the root’s key 22. Since 32 is greater than 22 so we move towards right subtree of the tree rooted at 22. Now we compare 32 with 37. Since 32 is less than 37 so we move towards left subtree of the tree rooted at 37. Now we compare 32 with 29. Since 32 is greater than 29 so we move towards right subtree of the tree rooted at 29 and since there is no further nodes to be checked, so we insert this new element as the right child of this node. The resulting search tree is shown in Figure-l4(b).

Figure l4

Here is the algorithm which inserts a new node into a binary search tree.

Algorithm : TreeInsert

TreeInsert(&Root, item)

Here Root contains the address of root node. The value of Root is passed by reference (pointer to pointer) in order to allow change in the insertion of a node.

Step-1 : If Root is NULL then create a new node and sets its field and assign it to Root and return back.
Step-2 : If ((Root ->data > item) then
call TreeInsert(&((*Root)->lchild), item)
Else if  ((Root ->data V item) then
call TreeInsert(&((*Root)->rchild), item)
Else print an error message – “No two nodes can have same value.”
Step-3 : Exit.

Here is the ‘C’ implementation of this algorithm.

Implementation : TreeInsert

TreeInsert(TreeNode **Root, int item)
{
 if (*Root == NULL)
 {
 *Root = getnode();
 (*Root)->data = item;
 (*Root)->lchild = NULL;
 (*Root)->rchild = NULL;
 return;
 }
 if ((*Root)->data > item)
 TreeInsert(&((*Root)->lchild), item);
 else if ((*Root)->data < item)
 TreeInsert(&((*Root)->rchild), item);
 else
 {
 printf("\nError : No two nodes have same key value.\n");
 exit(0);
 }
}

As this function is also tail recursive, it is easy to replace recursion with iteration.

Here is the non-recursive insertion algorithm.

NonRecTreeInsert(TreeNode **Root, int item)
{
 TreeNode *temp, *current;

 temp = getnode();
 temp->data = item;
 temp->lchild = NULL;
 temp->rchild = NULL;

 if (*Root == NULL)
 {
 *Root = temp;
 return;
 }
 current = (*Root);
 while (current != NULL)
 {
 if (current->data > item)
 {
 if (current->lchild != NULL)
 current = current->lchild;
 else
 {
 current->lchild = temp;
 return;
 }
 }
 else if (current->data < item)
 {
 if (current->rchild != NULL)
 current = current->rchild;
 else
 {
 current->rchild = temp;
 return;
 }
 }
 else
 {
 printf("\nError : No two nodes have same key value.\n");
 exit(0);
 }
 }

}

Deletion from a Binary Search Tree

Now I am writing how to delete a node from a binary search tree. Deletion of a node from a binary search tree is more complex than searching in a binary search tree or insertion of a node into a binary search tree. When we delete a node we will search it first and then delete it.

There are four possibilities:

1.    The deleted node is a leaf node
2.    The deleted node has only right child
3.    The deleted node has only left child
4.    The deleted node has both children

If the node to be deleted is a leaf node the only task in this case is to be done is to reset the respective pointer of its parent to NULL, as shown in Figure-l5(a). Even the node to be deleted has one child only then the deletion process is very simple. In this case we adjust the link from the parent of the deleted node to point to its non-empty subtree as shown in figure-l5(b) and figure-l5(c). But the situation becomes complex when the node to be deleted has both left and right subtrees non-empty, as shown in Figure-l6.

When the node to be deleted has both left and right subtrees non-empty, we first replace the node to be deleted either the largest element in the left subtree or the smallest element in the right subtree. And then we proceed to delete this replacing node from the subtree from which it was taken.

Figure l5

For example, let we want to delete the element 40 in the tree shown in figure-l6(a). Here we will replace it by either the largest element ‘30’ in its left subtree or the smallest element ‘51’ in its right subtree. Suppose we opt the smallest element in the right subtree as shown in figure-l6(b). For this we will need to find the inorder successor of a node to be deleted. Inorder successor of a node is found out by first going to its right child and then continually going to left as long as an empty subtree is encountered. The inorder successor of element 40 is 51. So now we replace the data of the node to be deleted by the data of the inorder successor node. Once the element is replaced, we must delete the inorder successor. The inorder successor of any node with two children can have at most one child because it can not have a non-empty left subtree. In this case since 51 has no child, the pointer from its parent is set to NULL. Figure-l6(b) shows the resultant tree after deleting element 40.

Figure l6

Here is the algorithm, which deletes the specific node from a binary search tree.

Algorithm : TreeDelete

TreeDelete(&Root, item)

Here Root contains the address of root node. The value of Root is passed by reference (pointer to pointer) in order to allow change after the deletion of a node.

1.    If Root is NULL then print an error message and go to step-12.
2.    Set current to Root node and father to NULL
3.    Repeat through step-6 while ((current != NULL)&&(current->data != item))
4.    Update father = current
5.    If (current->data > item) then current = current->lchild
6.    Else current = current->rchild
7.    Check the value of current. If current is NULL then print an error message and go to step-12; otherwise go to step-8
8.    If the current node has both children then replace the data field of current node with its inorder successor node ‘succ’.
9.    Set current = succ
10.    If the current node has one child only then set the father’s link appropriately
11.    Free the memory space occupied by current node
12.    Exit.

Here is the ‘C’ implementation of this algorithm.

Implementation : TreeDelete

TreeDelete(TreeNode **Root, int item)
{
 TreeNode *current, *father, *succ;
 if (*Root == NULL)
 {
 printf(“\nEmpty Tree.”);
 return;
 }
 current = (*Root);
 father = NULL;
 while ((current != NULL)&&(current->data != item))
 {
 father = current;
 if (current->data > item)
 current = current->lchild;
 else
 current = current->rchild;
 }
 if (current == NULL)
 {
 printf("\nItem does not exit.\n");
 return;
 }
if ((current->lchild != NULL)&&(current->rchild!=NULL))   /* if current has both children */
 {
 father = current;
 succ = current->rchild;
 while (succ->lchild != NULL)
 {
 father = succ;
 succ = succ->lchild;
 }
 current->data = succ->data;
 current = succ;
 }
if (current->lchild == NULL)                /* if current has only right child */
 {
 if (father != NULL)
 {
 if (father ->lchild == current)
 father->lchild = current->rchild;
 else
 father->rchild = current->rchild;
 }
 else
 (*Root) = current->rchild;
 }
else if (current->rchild == NULL)            /* if current has only right child */
 {
 if (father != NULL)
 {
 if (father ->lchild == current)
 father->lchild = current->lchild;
 else
 father->rchild = current->lchild;
 }
 else
 (*Root) = current->lchild;
 }
 freenode(current);
 return;
}