3. (20 points) If you are familiar with how to draw a computation tree for recursive function calls or a computation tree' after the elimination of tail recursion, you may skip this part and proceed to the questions (a), (b), and (c) directly Consider the following recursive function for solving the Tower of Hanoi problem: void ToH(int n, char src, char intm, char dest) if (n1) printf ("move return; %d from %c to %c ", n, src, dest); ToH (n - 1, src, dest, intm); printf("move %d from %c to %c ", n, src, dest) ; ToH(n - 1, intm, src, dest); The following figure shows the computation tree when the following statement is executed ToH (3, ''c In this computation tree, each node is labeled with the arguments passed to the function. The tail recursion in the function ToH can be eliminated as follows: void iter_ToH (int n, char src, char intm, char dest) while (n !-1) iter ToH(n - 1, src, dest, intm); printf ("move %d from %c to %c ", n, src, dest); char tmp-intm intm- src; srctmp n=n-1; printf("move %d from %c to %c ", n, src, dest) ; With the tail recursion removed, we have a computation tree that shows the iterations as horizontal branches (a) (7 points) Consider a binary tree implemented with the following structure: typedef struct _tnode char info; struct_tnode left; struct tnode *right; tnode Suppose you have a binary tree as follows, where the letter in the node is the info stored in the node: Now, we pass the root node 'A' to the following recursive preorder function: void preorder(tnode ode) if (nodeNULL) return; printf ("%cla", node-label); preorder (node->left); preorder (node->right); Draw the computation tree corresponding to the recursive calls of preorder (in the space provided next page). Each node of the computation tree should be labeled with the info field ifa non-NULL tnode is passed to the function. If a NULL pointer is passed to the function, the node in the computation tree should be labeled with NULL Indicate on the computation tree a chain of recursive calls that result in the most number of stack frames for the function preorder on the call stack. (b) (6 points) Modify the preorder function to eliminate the tail recursion. void iter-preorder (tnode snode) (e) (7 points) Draw the computation tree' corresponding to the recursive functioniter_preorder when it is called with the same binary tree shown in (a) Indicate on the computation 'tree' a chain of recursive function calls that result in the most number of stack frames for the function iter-preorder on the call stack. 3. (20 points) If you are familiar with how to draw a computation tree for recursive function calls or a computation tree' after the elimination of tail recursion, you may skip this part and proceed to the questions (a), (b), and (c) directly Consider the following recursive function for solving the Tower of Hanoi problem: void ToH(int n, char src, char intm, char dest) if (n1) printf ("move return; %d from %c to %c ", n, src, dest); ToH (n - 1, src, dest, intm); printf("move %d from %c to %c ", n, src, dest) ; ToH(n - 1, intm, src, dest); The following figure shows the computation tree when the following statement is executed ToH (3, ''c In this computation tree, each node is labeled with the arguments passed to the function. The tail recursion in the function ToH can be eliminated as follows: void iter_ToH (int n, char src, char intm, char dest) while (n !-1) iter ToH(n - 1, src, dest, intm); printf ("move %d from %c to %c ", n, src, dest); char tmp-intm intm- src; srctmp n=n-1; printf("move %d from %c to %c ", n, src, dest) ; With the tail recursion removed, we have a computation tree that shows the iterations as horizontal branches (a) (7 points) Consider a binary tree implemented with the following structure: typedef struct _tnode char info; struct_tnode left; struct tnode *right; tnode Suppose you have a binary tree as follows, where the letter in the node is the info stored in the node: Now, we pass the root node 'A' to the following recursive preorder function: void preorder(tnode ode) if (nodeNULL) return; printf ("%cla", node-label); preorder (node->left); preorder (node->right); Draw the computation tree corresponding to the recursive calls of preorder (in the space provided next page). Each node of the computation tree should be labeled with the info field ifa non-NULL tnode is passed to the function. If a NULL pointer is passed to the function, the node in the computation tree should be labeled with NULL Indicate on the computation tree a chain of recursive calls that result in the most number of stack frames for the function preorder on the call stack. (b) (6 points) Modify the preorder function to eliminate the tail recursion. void iter-preorder (tnode snode) (e) (7 points) Draw the computation tree' corresponding to the recursive functioniter_preorder when it is called with the same binary tree shown in (a) Indicate on the computation 'tree' a chain of recursive function calls that result in the most number of stack frames for the function iter-preorder on the call stack