Inorder and Preorder traversals of a Binary Tree given output the Postorder traversal of it.

Inorder and Preorder traversals of a Binary Tree given output the Postorder traversal of it.

Input:
In-order traversal in[] = {4, 2, 5, 1, 3, 6}
Pre-order traversal pre[] = {1, 2, 4, 5, 3, 6}

Output:
Post-order traversal is {4, 5, 2, 6, 3, 1}

We can print post-order traversal without constructing the tree. 

1. Root is always the first item in preorder traversal and it must be the last item in postorder traversal.
   - Here take 1.
2. We first recursively print left subtree, then recursively print right subtree.
   - From In-Order take Left nodes of root as left subtree and right nodes as right subtree
   - eg here 4,2,5 as Left subtree and 3,6 Right subtree of 1.
   - Check Pre-order here U can understand 2 is root of left subtree and and at left of 2 all nodes will be at left subtree and right of 2 are right subtree of 2.
   they are 4, and 5.
3. Print left subtree first.
4. Same traverse for right subtree of 1 and u'll find 3 as root of right subtree and 6 as right subtree of 3.
5. print this right subtree.

         1
      /     \   
     2       3
   /   \      \
  4     5      6

Code




#include <iostream> using namespace std;

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] << " ";
}