Portorder and inorder!!!

Question:

Given Postorder and Inorder traversals of a Binary tree(not BST),
find the Preorder traversal.

Can any one explain or provide a pseudocode for this question?

Answer:

Let PO array contains Postorder Traversal.
Let IN array contains Inorder Traversal.
Let PRE be the required array.

1) Take Last number of the of the PO array. This will be the first element of PRE array.
2) Now search this element in IN array and find its position. (Simple Linear Search)
3) Now consider the left part and right part of the searched element in IN array.
4) Now start searching the first element from the number obtained in 1st step in PO array which is first found in left part of the IN array obtained above. This will be the next element of IN array.Do this procedure recursively.
5) Now start searching the first element from the number obtained in 1st step in PO array which is first found in the right part of the IN array obtained in 3rd step. This will be the next element of IN array.Do this procedure recursively.

T.C. O(n^2)

For given traversals;

Preorder : AB
Postorder : BA

A is root node 


so tree will always be
A
/
B

Remember preorder and postorder principles

For Preorder its - Root, Left and Right
For Postorder its - Left, Right and Root

Preorder = root [ left subtree ] [ right subtree ]

Postorder = [ left subtree ] [ right subtree ] root

You take any of let or right part to be empty and you will generate two trees
i.e.
Let X be a subtree and not a node
....A
./
X

or

A
..\
...X

now in first one: Pre = A [ X ] [ null ] && Post = [ X ] [ null ] A
Similarly in second one Pre = A [ null ] [ X ] && Post = [ null ] [ X ] A