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