536

Tree Recursion

#include <iostream>

#include <stdio.h>
#include <string.h>
#include <string>

using namespace std;

// A utility function to search x in arr[] of size n
int search(char arr[], char 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(char in[], char 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];
}

// Driver program to test above functions
int main()
{
char in[28];
char pre[28];
while(scanf("%s %s",pre,in) == 2)
{
int n = strlen(in);

//printf("%d\n",search(in, pre[0], n));
//cout<<n<<"\n";
//cout << "Postorder traversal " << endl;
printPostOrder(in, pre, n);
cout<<"\n";
}

return 0;
}