tree reconstruction

[sophia]

Dear all,

Is it possible to re create a binary tree from given preorder and post
order traversals ?

 

[Walter Roberson]

Is it possible to re create a binary tree from given preorder and post
order traversals ?

Yes.

Look for,
"An optimal parallel algorithm to reconstruct a binary tree from its
traversals" by Stephan Olariu, Michael Overstreet and Zhaofang Wen

 

[Ben Pfaff]

Is it possible to re create a binary tree from given preorder and post
order traversals ?

I believe that there is an exercise in Knuth vol. 1 on this topic
or one closely related. I imagine that it has an answer, too.

 

[Antoninus Twink]

Yes.

Well...

There's an ambiguity as soon as you have a node with no left descendant
or no right descendant. For example,

a and a
/ \
b b

both have preorder ab and postorder ba.

Of course, these trees are really the same, for some interpretation of
"really the same".

 

[sophia]

Yes.

Look for,
"An optimal parallel algorithm to reconstruct a binary tree from its
traversals" by Stephan Olariu, Michael Overstreet and Zhaofang Wen

where to get free copy of the above

 

[Walter Roberson]

where to get free copy of the above

You might find a linear version more useful,

http://citeseer.ist.psu.edu/andersson90construction.html

Construction of a Tree from its Traversals in Optimal Time and Space (1990)
Arne Andersson, Svante Carlsson

http://citeseer.ist.psu.edu/166720.html

Constructing a Binary Tree Efficiently from Its Traversals (1998)
Erkki Makinen