binary tree traversal
Author Message
binary tree traversal

hi
this is slightly off topic but...
given preorder and inorder traversals of a binary tree
can we find the postorder.......

ankur pruthi

Thu, 01 Jan 2004 04:36:25 GMT
binary tree traversal

Quote:
> hi
> this is slightly off topic but...
> given preorder and inorder traversals of a binary tree
> can we find the postorder.......

> ankur pruthi

Agreed, this _is_ OT.

Cheers, and thanks for this nice little puzzle

--
T. Haupt

Thu, 01 Jan 2004 03:05:08 GMT
binary tree traversal

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.

Thu, 01 Jan 2004 05:39:47 GMT
binary tree traversal

Quote:

> given preorder and inorder traversals of a binary tree
> can we find the postorder.......

This is Exercise 2.3.1-6 in Knuth's _TAOCP_, volume 1.

Thu, 01 Jan 2004 09:05:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages