## Assignment 8

### The exercise

Consider a binary tree with each node carrying a (unique) label. In-order and pre-order listings of these labels are defined by the following recursive procedures:

```inorder ( node )
{
if (node != NULL) {
inorder(left child of node);
print(label of node);
inorder(right child of node);
}
}

preorder ( node )
{
if (node != NULL) {
print(label of node);
preorder(left child of node);
preorder(right child of node);
}
}
```
A binary tree and the in-order and pre-order listings of the labels of its nodes are shown in the following figure:

Given the in-order and pre-order listings for a binary tree, the tree can be uniquely reconstructed using the following recursive algorithm:

```construct ( inlist , prelist )
{
if (inlist and prelist are both non-empty) {
create a new node;
set the label of the new node to be the first label of prelist;
locate this label in inlist;
let m be the number of labels in inlist before this location;
let n be the number of labels in inlist after this location;
let leftinlist be the first m labels of inlist;
let rightinlist be the last n labels of inlist;
let leftprelist be the second through (m+1)st labels of prelist;
let rightprelist be the last n labels of prelist;
left child of new node = construct (leftinlist, leftprelist);
right child of new node = construct (rightinlist, rightprelist);
return(new node);
}
return(NULL);
}
```

Implement this construct procedure. Read the inlist and prelist from the user, construct the tree and print it.

### Sample output

```Inorder listing  : bfdgaehc
Preorder listing : abdfgceh
Node : a, Left child :    b, Right child :    c.
Node : b, Left child : NULL, Right child :    d.
Node : d, Left child :    f, Right child :    g.
Node : f, Left child : NULL, Right child : NULL.
Node : g, Left child : NULL, Right child : NULL.
Node : c, Left child :    e, Right child : NULL.
Node : e, Left child : NULL, Right child :    h.
Node : h, Left child : NULL, Right child : NULL.
```

### Test input

Show the output of your program on the following inputs:
```Inorder listing  : GDHBAECF
Preorder listing : ABDGHCEF

Inorder listing  : abcdefghijkl
Preorder listing : abcdefghijkl

Inorder listing  : abcdefghijkl
Preorder listing : lkjihgfedcba

Inorder listing  : abcdefghijkl
Preorder listing : badcfehgjilk

Inorder listing  : cbafedihglkj
Preorder listing : abcdefghijkl

Inorder listing  : abcdefghijkl
Preorder listing : bcdefghijkla

Inorder listing  : bcdefghijkla
Preorder listing : abcdefghijkl

Inorder listing  : hdibjekalfmcngo
Preorder listing : abdhiejkcflmgno

Inorder listing  : ABCDEFGHIJKLMN
Preorder listing : HGFEDCBAIJKLMN

Inorder listing  : ABCDEFGHIJKLMN
Preorder listing : GABCDEFNMLKJIH
```