Assignment:

Question 1: Describe a recursive algorithm that counts the number of nodes in a singly linked list.

Solution 1:

Introduction

 Here before writing the algorithm we must understand the word "Recursion". This word has come from "Recur" which means, "Happen again and again". A more interesting definition of this word is given in "The New Hacker's Dictionary". For example in mathematics, factorial is a recursive function because it is defined as bellow:

 Now to calculate N! we have to calculate (N-1)! until we get 0 to return 1. This was a simple example so you might think of using loops but in some complex problems, like tree related problems, recursion we makes the logic simpler to understand. Let's now come to our problem. We may define a solution like the one we have discussed in the above paragraph:

Algorithm

1. Start function count with parameter list
2. If list is NULL then count is 0 so store 0 to result and return out of the function
3. call function count with the reference to next node as parameter and store returning value + 1 to result and return out of the function
4. Stop

1. Function count(list)
2. If list = NULL then return count := 0
3. return count := 1 + count(next node of list)
4. End of function count(list)

Program

01 int count(struct node *lst){
02	return (lst==NULL) ? 0 : (1 + count(lst->next));
03 }

Conclusion

 Recursion is a good technique to simplify the logic but it could lead to program crash due to stack overflow if not used carefully. We should not use the technique where the logic is already simple and can be easily applied with other simple techniques like looping. Although this problem was not as complex as to be solved with recursion, we did it just because the assignment tells us to do.

Question 2: Draw a Binary Tree T such that

• Each internal node of T stores a single character.
• A preorder traversal of T yields EXAMFUN
• A An in order traversal of T yields MAFXUEN

Solution 2:

Introduction

 Before building a tree according to the given orders of traversal, we should first study the properties of different orders of traversal. Look at the table below:

Pre-order Traversal	AB	AB	First node is definitely the root but uncertain about left and right child.
In-order Traversal	BA	AB	If root is known then it is certain about left and right child otherwise unpredictable.
Post-order Traversal	BA	BA	Last node is definitely the root but uncertain about left and right child.

 To build a tree we must know two things. The first one is all the roots of the tree and sub trees and the second is the information about which sub tree (or node) is in left of the root and which one is in right of it. As we have seen in the above table that pre-order or post-order of a tree may help us in finding the roots of the tree and all its sub trees and in-order can tells us everything else. Therefore, to build a tree we need to have the in-order of the tree and any of the pre-order or post-order. Even we may also work with only in-order if we could find the information about roots through some other means like operator precedence in expression trees etc. So now, let's build up the tree!

Building the Tree

 Now since we know that the first node of the pre-order of a tree is its root we can easily locate the root node in the in-order of that tree like this:
 

Pre-order:	EXAMFUN
In-order:	MAFXUEN

Now it is clear by looking at the in-order that this tree has the root (E) with a node (N) in its right and a sub tree in its left whose in-order is (MAFXU). Let me depict it for a better understanding. The tree is looking like the figure below, as we have understood it so far.

 Now we have another sub tree to be expanded but this time we only know its in-order but we can get its pre-order too. Since we know that in pre-order we can find the left sub tree just after the root and we also know that this sub tree has 5 nodes so we just have to extract 5 nodes from (EXAMFUN) after the root node (E). Now we have:
 

Pre-order:	XAMFU
In-order:	MAFXU

Now we can easily get the next stage of our tree just as we have done so far. Look at the figure below. This is what we have got.

 Simply like before we have yet another sub tree the pre-order and in-order of whose are as below:
 

Pre-order:	AMF
In-order:	MAF

 In this way we can construct any tree using its in-order traversal with either its pre-order or post-order or some other information indicating the roots. The logic we have just used is recursive so I implemented it in a 'C' program. My achievement with this program is that I got the whole program run in a single shot, without any errors. The listing of it is as follows:

Program

01 #include<stdio.h>
02 #include<stdlib.h>
03 
04 #define MAXNODE 20
05 
06 typedef struct Tree_Templ
07 {
08         char Data;
09         struct Tree_Templ *Left;
10         struct Tree_Templ *Right;
11 } Tree;
12 
13 int SplitBranches(      char *InOrder, char *PreOrder,
14                         char **LeftIn, char **LeftPre,
15                         char **RightIn, char **RightPre ){
16 char *RootPos;
17         RootPos = (char *)strchr(InOrder, *PreOrder);
18 
19         *LeftIn = (char *)malloc(sizeof(char) * (RootPos - InOrder + 1));
20         strncpy(*LeftIn, InOrder, (RootPos - InOrder));
21         *(*LeftIn + (RootPos - InOrder)) = '\0';
22 
23         // strlen(RootPos) - 1(Root) + 1(for \0)
24         *RightIn = (char *)malloc(sizeof(char) * strlen(RootPos));
25         strcpy(*RightIn, (RootPos+1));
26 
27         *LeftPre = (char *)malloc(sizeof(char) * (RootPos - InOrder + 1));
28         strncpy(*LeftPre, PreOrder+1, (RootPos - InOrder));
29         *(*LeftPre + (RootPos - InOrder)) = '\0';
30 
31         // strlen(RootPos) - 1(Root) + 1(for \0)
32         *RightPre = (char *)malloc(sizeof(char) * strlen(RootPos));
33         strcpy(*RightPre, (PreOrder+1+strlen(RootPos)));
34 return 0;
35 }
36 
37 Tree *GenTree(char *InOrder, char *PreOrder){
38 Tree *Root;
39 char *LeftIn, *LeftPre, *RightIn, *RightPre;
40         if(InOrder == '\0')     return NULL;
41         Root = (Tree *)malloc(sizeof(Tree));
42         if((int)strlen(InOrder) == 1){
43                 Root->Data = *InOrder;
44                 Root->Left = Root->Right = NULL;
45         }
46         else{
47                 SplitBranches(  InOrder, PreOrder, &LeftIn,
48                                 &LeftPre, &RightIn, &RightPre   );
49                 Root->Data = *PreOrder;
50                 Root->Left = GenTree(LeftIn, LeftPre);
51                 Root->Right = GenTree(RightIn, RightPre);
52                 free(LeftIn);
53                 free(LeftPre);
54                 free(RightIn);
55                 free(RightPre);
56         }
57 return Root;
58 }
59 
60 int Traverce(Tree *Node){
61         if(Node==NULL) return 0;
62         Traverce(Node->Left);
63         Traverce(Node->Right);
64         putchar(Node->Data);
65 return 0;
66 }
67 
68 main(){
69 Tree *Root;
70 char InOrder[MAXNODE], PreOrder[MAXNODE];
71         printf("Give Inorder:\t\t");
72         scanf("%s", InOrder);
73         printf("Give Preorder:\t\t");
74         scanf("%s", PreOrder);
75 
76         Root = GenTree(InOrder,PreOrder);
77 
78         printf("The Postorder is:\t");
79         Traverce(Root);
80         printf("\n");
81         getchar();
82         getchar();
83 return 0;
84 }

Conclusion

 This assignment taught us the importance of the in-order traversal because using this traversal, with some rules to find roots (like operator precedence), we can easily generate the tree. This has its application in expression evaluation and other searching sorting techniques. We can also easily modify the above program with a little change to evaluate the arithmetic expression.