4
$\begingroup$

Is there a way to reconstruct a binary tree just from its in-order representation?

I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and preorder representations, but none for only inorder.

$\endgroup$

migrated from cstheory.stackexchange.com Jul 19 '12 at 2:08

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ See also this question (which doesn't explain why in-order isn't enough on its own). $\endgroup$ – Gilles Jul 19 '12 at 8:48
6
$\begingroup$

**Example Trees**

The in-order traversal is not unique. The above trees have the same sequence 1,2,3,4,5. (They are isomorphic, but I assumed you consider ordered binary trees.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy