Print Postorder traversal from given Inorder and Preorder traversals

Problem:
Given Inorder and Preorder traversals of a binary tree, print Postorder traversal.

Example:

Input:
Inorder traversal in[] = {4, 2, 5, 1, 3, 6}
Preorder traversal pre[] = {1, 2, 4, 5, 3, 6}

Output:
Postorder traversal is {4, 5, 2, 6, 3, 1}

Trversals in the above example represents following tree

         1
      /     \   
     2       3
   /   \      \
  4     5      6

Solution:
A naive method is to first construct the tree, then use simple recursive method to print postorder traversal of the constructed tree. We can print postorder traversal without constructing the tree.

1. The pre[0] is the root of the tree --> 1
2. The in[] represents the tree as:
   
   { { left-sub-tree } ;  root ;   { right-sub-tree } }
   
   So the index of the root at in[] is the length of the left sub-tree --> 3
3. The (in[].length - rootIndex - 1) is the length of the right sub-tree --> 2
4. The pre[] represents the tree as:
   
   { root ;   { left-sub-tree } ;  { right-sub-tree } }
   
   Since we know the lengths of the sub-trees from steps #2 and #3, we can proceed recursively as follows:
   
   leftIn[] = in[ 0 .. (rootIndex-1) ] = { 4, 2, 5 }
   leftPre[] = pre[ 1 .. (rootIndex-2) ] = { 2, 4, 5 }
   
   rightIn[] = in[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   rightPre[] = pre[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   
   Recursion ends when the lengths of the in[] and pre[] become equal to 1.

int search(int arr[], int x, int n)
{
    for (int i = 0; i < n; i++)
      if (arr[i] == x)
         return i;
    return -1;
}
 
// Prints postorder traversal from given inorder and preorder traversals
void printPostOrder(int in[], int pre[], int n)
{
   // The first element in pre[] is always root, search it
   // in in[] to find left and right subtrees
   int root = search(in, pre[0], n);
 
   // If left subtree is not empty, print left subtree
   if (root != 0)
      printPostOrder(in, pre+1, root);
 
   // If right subtree is not empty, print right subtree
   if (root != n-1)
      printPostOrder(in+root+1, pre+root+1, n-root-1);
 
   // Print root
   cout << pre[0] << " ";
}

Complexity:

time - O(n^2)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/