How many tree travelsals needed to reconstruct a binary tree?

0
votes

How many tree traversals (preorder, inorder, postorder) do I need at least to reconstruct a binary tree. I am pretty sure it is two, however I have problems in explaining why. I would also say that a reconstruction is possible with every combination of these 3 types.

Would be great if somebody could give me a proper explanation;).

1
binary-treetree-traversal
When you say reconstruct what exactly do you mean? - Ely Fialkoff
Ok, here is an example. Inorder: 9 3 10 2 1 5 4 7 6 8, Preorder: 1 2 3 9 10 4 5 6 7 8 now I am supposed to draw a binary tree out of this information. The question is how many notations I need at least to draw the tree. - Jenew
if you know the ordering (inorder, preorder or postorder) why can't you just create the tree right away? - Ely Fialkoff

1 Answers

1
votes

If you only have one traversal (eg. inorder), you cannot reconstruct a unique tree. You can explain by giving example.

Suppose inorder traversal of a tree is: ABC. Then there can be many trees that can be reconstructed from this:

A               B                C
 \             /  \             /
  B           A    C           B
   \                          /
    C                        A

Therefore, you need 2 traversals to uniquely reconstruct a tree uniquely.