Quote:

>hi

>this is slightly off topic but...

>given preorder and inorder traversals of a binary tree

>can we find the postorder.......

I believe that given preorder and inorder traversals, you can find the

exact shape of the tree, and if you have that tree, you can find

various postorders. (Note that there is no unique preorder or postorder

because you can visit the left or right children in any order).

I believe that an algortihm exists for processing the preorder

and inorder lists which will find the tree.

Suppose that the last four elements of the preorder traversal

are W X Y Z. It's clear that Z is the root of the tree, and

Y is its immediate child.

Z Z

Y Y

So Y can be in one of two positions. To disambiguate which, consult the

inorder. If Y appears before Z in the inorder, then the left choice is

right, otherwise the right one.

Having a partial tree, proceed with the next node from the left, X.

This node X is either the immediate child of Z, complementing Y, or it

is a left child of Y, or it is a right child of Y. There are now three

candidate positions. Only one of these positions satisfies the inorder.

If X is greater than both Y and Z, then it must be in the rightmost

position. If X is between Y and Z, it must be in the middle position.

If X is less than Y or Z, it must be in the leftmost position.

Inductive hypothesis: for each new node, the number of places where it

can be inserted is one greater than for the previous insertion, and the

inorder list will uniquely determine which place is correct.

I believe that all the empty candidate positions can be treated

as paremeters, and that at an inorder traversal of the partial tree

can be done in which these parameters are explicit. Then the

new node is placed into the list, substituting for that parameter.

For example if you have

Z

Y

X

Then the empty positions can be numbered:

Z

Y 4

1 X

2 3

Now construct an inorder from this, making the parameters explicit:

1 Y 2 X 3 Z 4

Take the next node W from the preorder, and figure out whether

it fits under 1, 2, 3 or 4. Only one of these will put

X, Y Z and W in the correct order. Then index the parameter

back into the tree and put the node there.

And so we can process all th enodes one by one and construct

a tree that is uniquely determined by the inorder and postorder

litss.

That should give you enough pieces for a proof to complete your homework.