0

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.

sbrajagopal26
  • 13

1 Answers1

0

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:

Pre-order: a,b
Post-order: b,a

We know a is the root, but we can't comment on whether b is the left child or the right child of a.

John Doe
  • 111
  • yes sir..i have read that a unique solution cannot be obtained if only preorder and post order is given ..unique solution is only possible if inorder+(preorder or postorder) were given.. but i am sure about this question – sbrajagopal26 Jul 02 '13 at 15:16
  • Perhaps further insights into the implication of the keyword "rooted" might help settle the dispute. I don't have a strong mathematical background, but in the world of programming and data structures, a rooted tree is one where you have a root node, a node without a parent. I don't think I can solve this without more knowledge. – John Doe Jul 02 '13 at 15:39
  • thanks thankyou for your time ..appreciate it – sbrajagopal26 Jul 02 '13 at 16:14