Prove that binary trees with the same inorder and preorder traversals are identical?

Question

Does anybody know how to prove that if two binary trees have the same inorder and preorder traversals, then they are identical? (perhaps by showing that you can't have two different binary trees with identical inorder and preorder traversals)

Alternatively, show a case that would disprove this, or show why can't it be done?

(I'll admit, this is purely academic but it's not homework or anything. My instincts tell me that it's true, but I don't think I ever did any proofs on graphs.)

Answer 1

The basic idea is how to reconstruct a binary tree by the given inorder and preorder traversals.

It's possible to reconstruct only one binary tree from the inorder and preorder traversals.

See:

• Nonrecursive algorithms for reconstructing a binary tree from its traversals (paper)
• reconstructing a tree from its preorder and postorder lists (SO question)