Postorder traversal from given Inorder and Preorder

Postorder traversal from given Inorder and Preorder

  September 08, 2017    

---

Idea:

As we know 1st element of a tree preorder will be last to postorder.
So we will print it at the end of every recursion.
We will search this element in inorder and recur for left and right subtree.

Base Case :

if index of root ==0  || n-1 it means we have gone with this tree

Recur for left and right sub tree with corresponding in & pre order for them.


Code:

  int s(int arr[],int n,int x) // for search index
    {
        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=s(in,n,pre[0]);
if(root!=0)
printPostOrder(in,Arrays.copyOfRange(pre,1,n),root);
if(root!=n-1)
printPostOrder(Arrays.copyOfRange(in,root+1,n),Arrays.copyOfRange(pre,root+1,n),n-root-1);
System.out.print(pre[0]+" ");
}