erjiang
Reputation: 45727
Prove that binary trees with the same inorder and preorder traversals are identical?
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.)
Upvotes: 11
Views: 9054
Answers (1)
Nick Dandoulakis
Reputation: 43130
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)
Upvotes: 5
Related Questions
- Uniqueness of Inorder, Preorder, and Postorder traversal with null elements
- Generating a binary tree using inorder and preorder traversal
- How to check if the given preorder ,inorder and postorder traversals are of the same binary tree?
- Binary tree from Preorder and inorder traversal
- Find the inorder traversal from its preorder traversal sequence in binary tree
- Proving that in-order traversal of binary search tree is sorted (without induction)
- construct a binary tree from in-order and level-order traversal
- How to find whether two trees are structurally same using level order traversal?
- sorted result of inorder traversal on binary tree
- Binary Tree from inorder and postorder