दिए गए इनऑर्डर और प्रीऑर्डर ट्रैवर्सल से पोस्टऑर्डर ट्रैवर्सल प्रिंट करें

एक ट्री प्रोग्राम के इनऑर्डर और प्रीऑर्डर के साथ दिए गए पोस्टरोडर ट्रैवर्सल को ढूंढना चाहिए और उसे प्रिंट करना चाहिए

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

एल्गोरिदम

START
Step 1 -> declare function as find_value(int p, int in_order[], int n)
   Loop For i=0 and i<n and ++i
      IF in_order[i]==p
         Return i
      End IF
   End
Step 2 -> declare function as postorder(int pre_order[], int in_order[], int n)
   Declare int variable as root = find_value(pre_order[0], in_order, n)
   IF root!=0
      Call postorder(pre_order+1, in_order, root)
   End
   IF root !=n-1
      Call postorder(pre_order+root+1, in_order+root+1,n-root-1)
   End
   Print pre_order[0]
End
Step 3 -> goto main()
   Declare int pre_order[] = {1, 2, 4, 5, 3, 6}
   Declare int in_order[] = {4, 2, 5, 1, 3, 6}
   Declare int size = sizeof(pre_order)/sizeof(pre_order[0])
   Call postorder(pre_order, in_order, size)
STOP

उदाहरण

#include <stdio.h>
int find_value(int p, int in_order[], int n) {
   for (int i = 0; i < n; ++i) {
      if (in_order[i] == p) {
         return i;
      }
   }
   return -1;
}
int postorder(int pre_order[], int in_order[], int n) {
   int root = find_value(pre_order[0], in_order, n);
   if(root !=0 )
      postorder(pre_order+1, in_order, root);
   if (root != n-1)
      postorder(pre_order+root+1, in_order+root+1, n-root-1);
   printf("%d ", pre_order[0]);
}
int main(int argc, char const *argv[]) {
   int pre_order[] = {1, 2, 4, 5, 3, 6};
   int in_order[] = {4, 2, 5, 1, 3, 6};
   int size = sizeof(pre_order)/sizeof(pre_order[0]);
   postorder(pre_order, in_order, size);
   return 0;
}

आउटपुट

यदि हम उपरोक्त प्रोग्राम चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा

4 5 2 6 3 1