Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order

For Inorder And Preorder traversals

inorder  = g d h b e i a f j c

preorder = a b d g h e i c f j

Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, "a" is the root of the tree; "gdhbei" are in the left subtree; "fjc" are in the right subtree. "b" is the next root; "gdh" are in the left subtree; "ei" are in the right subtree. "d" is the next root; "g" is in the left subtree; "h" is in the right subtree.
For Inorder and Postorder traversals
Scan postorder from right to left using inorder to separate left and right subtrees.

inorder   = g d h b e i a f j c

postorder = g h d i e b j f c a

Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.
For Inorder and Levelorder traversals
Scan level order from left to right using inorder to separate left and right subtrees.

inorder     = g d h b e i a f j c

level order = a b c d e f g h i j

Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.
Here is some working code which creates a tree out of the Inorder and Postorder
traversals. Note that here the tree has been represented as an array. This really simplifies the whole implementation.
Converting a tree to an array is very easy
Suppose we have a tree like this

      A

  B       C

 D E     F G

The array representation would be

a[1] a[2] a[3] a[4] a[5] a[6] a[7]

  A    B    C    D    E    F    G

That is, for every node at position j in the array, its left child will be stored at position (2*j) and right child at (2*j + 1). The root starts at position 1.
// CONSTRUCTING A TREE GIVEN THE INORDER AND PREORDER SEQUENCE

#include

#include

#include


/*-------------------------------------------------------------

* Algorithm

*

* Inorder And Preorder

* inorder = g d h b e i a f j c

* preorder = a b d g h e i c f j

* Scan the preorder left to right using the inorder to separate left

* and right subtrees. a is the root of the tree; gdhbei are in the

* left subtree; fjc are in the right subtree.

*------------------------------------------------------------*/

static char io[]="gdhbeiafjc";

static char po[]="abdgheicfj";

static char t[100][100]={'\0'};  //This is where the final tree will be stored

static int hpos=0;

void copy_str(char dest[], char src[], int pos, int start, int end);

void print_t();

int main(int argc, char* argv[])

{

  int i,j,k;

  char *pos;

  int posn;

  // Start the tree with the root and its

  // left and right elements to start off

  for(i=0;ihpos)hpos=pos;

}

void print_t()

{

  int i;

  for(i=1;i<=hpos;i++)

  {

    printf("\nt[%d] = [%s]", i, t[i]);

  }

  printf("\n");

}