Let T be a tree in which every nonleaf node has two children. Write a program to convert:

a) a preorder listing of T into a postorder listing,

b) a postorder listing of T into a preorder listing,

c) a preorder listing of T into an inorder listing

You need to use Python with Linked Lists! Here are the functions that you can use with Linked Lists. You don't need to create the Linked List, only the code for the above questions.

1. INSERT(x, p, L). Insert x at position p in list L, moving elements at p and following positions to the next higher position. That s, if L is ai, a2, . . . ,an, then L becomes ai, a2, . . . ,ap-i, x, ap, .. . ,an. If p is END(L), then L becomes al , a2, . . . ,an , x. If list L has no position p, the result is undefined 2. LOCATE(x, L). This function returns the position of x on list L. If x appears more than once, then the position of the first occurrence is returned. If x does not appear at all, then END(L) is returned 3. RETRIEVE(p, L). This function returns the element at position p on list L. The result is undefined if p = END(L) or if L has no position p Note that the elements must be of a type that can be returned by a func tion if RETRIEVE is used. In practice, however, we can always modify RETRIEVE to return a pointer to an object of type elementtype t Strictly speaking, the type is "LIST of elementtype" However, the implementations of lists we propose do not depend on what elementtype is; indeed, it is that independence that justifies the importance we place on the list concept. We shall use "LIST" rather than "LIST of elementtype" and similarly treat other ADT's that depend on the types of elements. 2.1 THE ABSTRACT DATA TYPE LIST 39 4. DELETE(p, L). Delete the element at position p of list L. If L is an. The result is undefined if L has no position p or if p END(L) 5. NEXT(p, L) and PREVIOUS(p, L) return the positions following and preceding position p on list L. If p is the last position on L, then NEXT(p,L) END(L). NEXT is undefined if p is END(L). PREVI. OUS is undefined if p is 1. Both functions are undefined if L has no posi- tion p returns position END(L) empty, the position returned is END(L,) 6. MAKENULL(L). This function causes L to become an empty list and 7. FIRST(L). This function returns the first position on list L. If L is 8. PRINTLIST(L). Print the elements of L in the order of occurrence