CS 61A Structure and Interpretation of Computer ProgramsSpring 2013 FinalINSTRUCTIONS• You have 3 hours to complete the exam.• The exam is closed book, closed notes, closed computer, closed calculator, except one hand-written 8.5” × 11”crib sheet of your own creation and the official 61A study guides attached to the back of this exam.• Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide abrief explanation.Last nameFirst nameSIDLoginTA & section timeName of the person toyour leftName of the person toyour rightAll the work on this examis my own. (please sign)For staff use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Q. 7 Total/12 /16 /8 /7 /8 /16 /13 /8021. (12 points) We Are Binary Tree HuggersThis problem makes use of the Tree class from lecture; its definition is contained in the Midterm 2 StudyGuide, attached to the end of this exam.(a) The depth of a tree is defined as the number of nodes encountered in the longest path from the root to aleaf. Complete the function definition below to compute the depth of a binary tree.def depth ( tree ):""" Compute the depth of a binary tree .>>> t = Tree (6 , Tree (2 , Tree (1)) , Tree (7))>>> depth ( t )3>>> t . left . right = Tree (4 , Tree (3) , Tree (5))>>> depth ( t )4"""if __ _ ___ ___ _ ___ ___ _ ___ ___ _ ___ ___ _ ___ ___ _ ___ ___ _ ___ ___ _ ___ ___ _ __ :return 1 + max ( ___ ___ _____ ___ ___ _____ ___ ___ __ ___ ___ _____ ___ _ ,__ _ ___ ___ ___ ____ ___ ___ ___ _ ___ ___ ___ _ ___ ___ ___ )__ _ ___ ___ _ ___ ____ ___ ____ ___ _ ___ ___ _ ___ ___ _ ___ ___ _ ___ ___ _ ___ ____ _(b) A binary tree is balanced if for every node, the depth of its left subtree differs by at most 1 from the depthof its right subtree. Fill in the definition of the is_balanced function below to determine whether or nota binary tree is balanced. You may assume that the depth function works correctly for this part.def is_balanced ( tree ):""" Determine whether or not a binary tree is bal anced .>>> t = Tree (6 , Tree (2 , Tree (1)) , Tree (7))>>> is_balanced (t)True>>> t . left . right = Tree (4 , Tree (3) , Tree (5))>>> is_balanced (t)False"""Login: 3(c) For the following class definition, cross out any incorrect or unnecessary lines in the following code so thatthe doctests pass. Do not cross out class declarations, doctests, or docstrings. You can crossout anything else, including method declarations, and your final code should be as compact as possible.Make sure to cross out the entire line for anything you wish to remove. You may assume thatthe depth and is_balanced functions are defined correctly in the global environment.class STree ( Tree ):""" A smart tree that knows its depth and whether or not it isbalan ced .>>> s = STree (6 , STree (2 , STree (1)) , STree (7))>>> s . depth3>>> s . i s_balancedTrue>>> s . left . right = STree (4 , STree (3) , STree (5))>>> s . depth4>>> s . i s_balancedFalse"""def __init_ _ ( self , entry , left = None , right = None ):Tree . __init__ ( entry , left , right )Tree . __init__ ( self , entry , left , right )self . entry = entryself . left = leftself . right = rightself . depth = depth ( self )self . i s_ ba la nc ed = i s_ ba lanced ( self )self . depth = depthself . i s_ ba la nc ed = i s_ ba lanced@proper tydef depth ( self ):return depth ( self )@proper tydef is_balanced ( self ):return is_balanced ( self )42. (16 points) Binary Tree Huggers are Environmentalists(a) (7 pt) Fill in the environment diagram that results from executing the code below until the entire program isfinished, an error occurs, or all frames are filled. You need only show the final state of each frame. You maynot need to use all of the spaces or frames. You may draw objects that are created but are not accessible fromthe environment, if you wish. Make sure to reflect every call to a user-defined function in the environmentdiagram.A complete answer will:• Add all missing names, labels, and parent annotations to all local frames.• Add all missing values created during execution.• Show the return value for each local frame.Global frame x x = [0, 1] y = list(map(lambda x: 2*x, x + [2])) y[2] = y z = y[:] z[2][2] = z Return Value Return Value Return Value Return Value Return Value list 0 1Login: 5(b) (9 pt) Fill in the environment diagram that results from executing the code below until the entire program isfinished, an error occurs, or all frames are filled. You need only show the final state of each frame. You maynot need to use all of the spaces or frames. You may draw objects that are created but are not accessible fromthe environment, if you wish. Make sure to reflect every call to a user-defined function in the environmentdiagram.A complete answer will:• Add all missing names, labels, and parent annotations to all local frames.• Add all missing values created during execution.• Show the return value for each local frame.Global frame eval def eval(expr): if type(expr) in (int, float): return expr procedure = expr[0] args, i = [], 1 while i < len(expr): args.append(eval(expr[i])) i += 1 return procedure(*args) expr = [lambda x: [x * x] + expr, 4] result = eval(expr) Return Value Return Value Return Value Return Value func eval(expr)63. (8 points) We Recurse at Hard ProblemsThe following are the first six rows of Pascal’s triangle:11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1The first and last element in each row is 1, and each of the other elements is equal to the sum of the elementabove it and to the left and the element above it and to the right. For example, the third element in the lastrow is 4 + 6 = 10, since 4 and 6 are the elements above it and to the left and right.(a) Define a function pascal that takes a row index n and an element index k as arguments and computesthe kth element in row n, with indexing beginning at 0 for both n and k. Do not compute factorial orany other combinatorial expression as part of your solution.def pascal (n , k ):""" Compute the kth element of the nth row in Pascal ’s triangl e .>>> pascal (5 , 0)1>>> pascal (5 , 2)10"""Login: 7(b) Fill in the pascal_gen function below, which returns an iterator over the elements in the nth row ofPascal’s triangle. Your solution should be self-contained; you may not use the pascal function definedin part (a).def pa sc al _g en (n ):""" Return an itera tor over all the elemen ts in …