Answers

1.  (a) E  (b) H
2.  Input restricted deque
3.  Check the stack is not empty.
4.  if (rear < M) rear <- rear + 1; else Rear <- 1;
5.  Deletion at the end/rear/right.
    To delete the last node you need a pointer to its predecessor.
    To obtain this you have to traverse the list starting from the first node.
6.  Bookwork - see notes.
7.  See notes.
8.  Bookwork - see notes.
9.  (a) a general tree (b) root (c) 2 (d) 2 (e) leaf (f) parent.
10. (a) 1 2 4 7 5 8 11 3 6 9 12 10
    (b) 4 7 2 5 11 8 1 3 12 9 6 10
    (c) 7 4 11 8 5 2 12 9 10 6 3 1
11. Inorder traversal should be 1 2 3 4 5 6 7 8 9 10 11 12
12. Bookwork - see notes.
13. A stack to store pointers to nodes that still have to be visited
    (and a "direction indicator" for postorder).
14. 1 + the number of nodes.
15. You can traverse it efficiently in inorder and preorder without using a stack.
16. As 19 with an extra boolean field "rtag".
17. See notes.
    Ltag does not have to be set nor left thread from inorder successor.
18. See notes.
19. Bookwork - see notes.
20. Bookwork - see notes.