### Generate Postorder traversal of Tree from Inorder and Preorder traversal of tree without generating Tree.

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}

1 / \ 2 3 / \ \ 4 5 6

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

- Root is always the first item in preorder traversal and it must be the last item in postorder traversal.

– Here take 1. - 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. - Print left subtree first.
- Same traverse for right subtree of 1 and u’ll find 3 as root of right subtree and 6 as right subtree of 3.
- print this right subtree.

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; } void printPostOrder(int in[], int pre[], int n) { int root = search(in, pre[0], n); if (root != 0) printPostOrder(in, pre+1, root); if (root != n-1) printPostOrder(in+root+1, pre+root+1, n-root-1); cout << pre[0] << " "; }