Ex. 2.4 Tree processing Let T be an arbitrary (NOT necessarily binary) tree. For each vertex v in T, let v.val already contain a pre-loaded number. a) Write a simple recursive DFS procedure that prints the .val numbers in postorder, so that T.val is printed last. { Part a) is intended to be a push problem," which is not an exercise that requires a stack, but is instead a relatively easy exercise designed to push you in the directed needed to solve part b). Please see if you can make that happen.\} Ch 2. Basic data structures: what, 20problems Exercises 143 b) Let backpack be a global identifier initially storing the number X. Write a simple postorder DFS procedure Rotate (T) that inputs the root of tree T as described above. Rotate (T) must leave the physical tree T unchanged, but must change the ,val entries in T so that a postorder printing of T 's new vertex assignments will produce a new sequence of numbers that begins with the value X and then continues with the original sequence printed in part a, so that the first element printed in part a is the second in the new sequence, and the second in a is now the third, etc. But T.val, which is printed last in part a, is no longer stored in T, and should be assigned to backpack. In the example, the input tree is on the right, and X=9. The second tree shows the rotated values so the the postorder printing of the new T gives the listing that is requested. Do not write out athe data and read it back into the tree. Hint: Think of walking along the tree edges of the tree to execute a DFS of T while wearing the backpack. Start the trip with X sitting in the backpack. At the postorder exit time of a vertex v, you printed v.val in part a. But what you want to do is remember its v.val and reassign it to the next vertex you postorder processed in a. And what do you assign to v.val? Answer: It should be the last number you printed in a before you reached v. So when you reach v in part b, where should v.val's new value be? Answer. It should be in your backpackl Conceptually, you crush this problem without thinking by changing the print statement in part a into a swap statement in part b. Begin with the code: global backpack initialized to the value X; procedure Rotate(i:T)