Data structures

You have a full binary tree, where each node is labeled with a distinct letter. (Recall that a binary tree is full if each non-leaf node has exactly two children.) Throughout this problem, we restrict attention to full binary trees. (3.1) (3 points) Someone has performed a postorder traversal, and gave you a list of the node labels. (For example, in the tree shown in Fig. 2(b), this is (i.c, j,d, k, a, b, h, g, e, f).) Is it generally possible to uniquely recover a full binary tree from its postorder sequence? If yes, explain how by presenting an algorithm for doing so. If no, draw two different labeled full binary trees where the postorder lists are the same. (3.2) (3 points) Repeat question (3.1), but this time list has been modified so that each leaf node has been "flagged to distinguish leaves from internal nodes. (For exam- ple, in the tree shown in Fig. 2(b), if we use "*" to indicate a leaf, this would be (i*, c*,j*, d*, k, a, b, h*, g*, e, f).) (3.3) (3 points) Repeat (3.1), but this time for an inorder traversal of a full binary tree. (For example, in the tree shown in Fig. 2(b), this would be (i,b,c,a, j, k, d, f, h, e,g).) (3.4) (3 points) Repeat (3.2), but this time for an inorder traversal of a full binary tree. (For example, in the tree shown in Fig. 2(b), this would be (i*,b,c*, a,j*, k,d*, f,h*, e,g*).) (3.5) (3 points) We won't ask you to solve the remaining case of a preorder traversal), but you suppose you discuss the unflagged case (3.1) with your best friend. (You both suspect that the evil Prof. Mount may put this question on a future exam.) This friend announces that the answer is "no" and tells you that there is a simple 6-node counterexample. Without even seeing the counterexample, you tell your friend this is wrong! How is this possible? (Assume for the sake of this problem that you are not a psychic.) b h 9 k