CODEWITHSUNDEEP
binary-treetree-traversal
Jenew
Jenew

Reputation: 39

How many tree travelsals needed to reconstruct a binary tree?

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;).

Upvotes: 0

Views: 277

Answers (1)

Syed Waris
Syed Waris

Reputation: 1074

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.

Upvotes: 1

Related Questions