Reconstructing Binary Trees Via Traversals
Recall the binary tree data structure; recall three algorithms for traversing the tree: the inorder traversal, the preorder traversal, and the postorder traversal.
1. Suppose you are given the preorder traversal and the inorder traversal of a binary tree. Can you reconstruct the tree? If so, give an algorithm for doing so and prove its correctness. If not, give a counter example. Note that a binary tree is not necessarily a binary search tree.
2. Suppose you are given the preorder and postorder traversals of a binary tree. Can you reconstruct the tree? If so, give an algorithm for doing so and prove its correctness If not, give a counter example.
3. Suppose you are given the preorder traversal of a binary tree. In addition, you are told that the tree is a binary search tree. Can you reconstruct the tree? If so, give an algorithm for doing so and prove its correctness. If not, give a counter example.