Menu
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.)
946
In general, the inorder traversal is equivalent to the postorder traversal if there are only left children, and the inorder traversal is equivalent to the preorder traversal if there are only right children. Save this answer.
For Inorder, you traverse from the left subtree to the root then to the right subtree. For Preorder, you traverse from the root to the left subtree then to the right subtree. For Post order, you traverse from the left subtree to the right subtree then to the root.
It is not possible to construct a general Binary Tree from preorder and postorder traversals (See this). But if know that the Binary Tree is Full, we can construct the tree without ambiguity. Let us understand this with the help of the following example.
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:
192
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
