Decide the picture of a rooted tree with pre-order $a,b,c,d,e,f,g,h$ and post-order $d,e,f,g,h,c,b,a$. Show that there always is a unique solution for a given pre- and post-order of a rooted tree.
My solution is:
a
/
b
/
c
/
(d,e,f,g,h)
Is this right for the given pre- and post-order? I need help to show how it's always unique for a given pre- and post-order.
Are you sure you have shared all information here? As far as I understand, you can't uniquely determine the structure of a tree given only the pre-order and post-order traversals (unless the tree is complete). For instance, if you have the following:
We know a is the root, but we can't comment on whether b is the left child or the right child of a.