Homework $09$ : Trees This week, we$$ve been introduced to our second recursively$-$defined data structure, trees! $($As a reminder, the f irst one was linked lists.$)$ Recall from lecture that a tree is either: $$ the empty tree, represented by None in Python, or $$ anode that points to other trees. Nodes usually contain some data as well. Important Note As trees have a natural recursive definition and structure, functions that operate on tree often have simple and elegant recursive definitions. For this homework, all of your function implementations must be recursive and you cannot use any iteration $($i$.$e$.$ for$/$while loops$).$ Part $1$: Simple Tree Functions In the starter code file, simple$\_$tree$\_$functions.py$,$ implement the following functions. $$ height$($t$)$ Returns the height of the tree t$.$ Returns$-1$ for the empty tree. $$ size$($t$)$ Returns the number of nodes in the tree t$.$ find$\_$min$($t$)$ Returns the minimum element contained within a node in the tree t$.$ Returns float$("$inf$")$ for the empty tree. $$ find$\_$max$($t$)$ Returns the maximum element contained within a node in the tree t$.$ Returns float$("-$inf"$)$ for the empty tree. $$ contains$($t$,$ k$)$ Returns True if and only if k is contained within one of the nodes of t $($returns False otherwise$).$ in$\_$order$($t$)$ Returns a list containing contents of each node in the tree in the order of an in$-$order traversal of the tree. $$ pre$\_$order$($t$)$ Returns a list containing contents of each node in the tree in the order of an pre$-$order traversal of the tree. $$ post$\_$order$($t$)$ Returns a list containing contents of each node in the tree in the order of an post$-$order traversal of the tree. $1$Examples $"""0/\backslash 14//\backslash 253""">>>$n$1=$TreeNode$(1,$left$=$TreeNode$(2))>>>$n$4=$TreeNode$(4,$left$=$TreeNode$(5),$right$=$TreeNode$(3))>>>$tree $=$ TreeNode$(0,$left$=$n$1,$right$=$n$4)>>>$height$($tree$)2>>>$size$($tree$)6>>>$find$\_$min$($tree$)0>>>$find$\_$max$($tree$)5>>>$contains$($tree$,3)$ True $>>>$contains$($tree$,6)$ False $>>>$in$\_$order$($tree$)[2,1,0,5,4,3]>>>$pre$\_$order$($tree$)[0,1,2,4,5,3]>>>$post$\_$order$($tree$)[2,1,5,3,4,0]$ Part$2$:Higher$-$OrderTreeFunctions Ahigher$-$orderfunctionisafunctionthatdoesat leastoneofthefollowing: $$takesoneormorefunctionsasarguments$,$or $$returnsafunctionasitsresult$.$ Inthispartof thehomework,wewillexploresomefunctionsthattakeother functionsas inputandalso operateontrees. Oftentimesthefunctionspassedtoourhigher$-$orderfunctionswill taketheformofalambdaexpression, $($e$.$g$.$lambdax:xTheseexpressionsprovideanelegantwayforustocreatesmallanonymousfunctions. Foralittlemoreinfoonlambdaexpressions,checkout: $$https:$//$docs$.$python.org$/3/$reference$/$expressions$.$html#lambda $$https:$//$www$.$w$3$schools.com$/$python$/$python$\_$lambda.asp Inthestartercodefile,higher$\_$order$\_$tree$\_$functions.py$,$ implementthefollowingfunctions. $$count$\_$failures$($pred$,$t$)2$Takesapredicatefunction$($afunctionthatreturnseitherTrueorFalse$)$pred$,$andreturnsthe numberofnodesinthetreetwhosedatafailsthepredicate. $$ Iftisanon$-$emptytreenode,thenitsdatafailsthepredicateif pred$($t$.$data$)$returnsFalse$.$tree$\_$map$($f$,$t$)$Takesafunctionf$,$andreturnsanewtreeconsistingofthenodesfromtsuchthatfhasbeen appliedtothedatawithineachofthenodesint.$$ThisfunctiondoesNOTmutatethetreet$,$ itreturnsanewtree. $$tree$\_$apply$($f$,$t$)$Takesafunctionf$,$andapplies ittothedataheldwitheachnodeofthetreet.$$Thisfunctionmutatesthetreet$.$ Examples $"""0/\backslash 14//\backslash 253""">>>$n$1=$TreeNode$(1,$left$=$TreeNode$(2))>>>$n$4=$TreeNode$(4,$left$=$TreeNode$(5),$right$=$TreeNode$(3))>>>$tree $=$ TreeNode$(0,$left$=$n$1,$right$=$n$4)$ #CountFailures $>>>$count$\_$failures$($lambda x:x$\%2==0,$tree$)3$ #$3$nodescontainintegersthatarenoteven $>>>$count$\_$failures$($lambda x:x tree$)2$ #$2$nodescontainintegersthatarenotlessthan$4>>>$count$\_$failures$($lambda x:x tree$)6$ #$6$nodescontainintegersthatarenotlessthan$0$ #TreeMap $>>>$another$\_$tree $=$ tree$\_$map$($lambda x:x$**2,$tree$)>>>$in$\_$order$($another$\_$tree$)[4,1,0,25,16,9]>>>$in$\_$order$($tree$)[2,1,0,5,4,3]$ #$$originaltreewasnotmutatedby tree$\_$map #TreeApply $>>>$tree$\_$apply$($lambdax:x$**3,$tree$)3>>>$ in$\_$order$($tree$)[8,1,0,125,64,27]$ # $$ original tree was mutated by tree$\_$apply Testing Note that we are not requiring unit tests in your submission. At this point in the semester, we expect that you are developing your own test suites for these questions as we do not provide any unit tests on Gradescope. Therefore, your tests will not be graded, but developing a thorough suite of tests is the only way that you will be able to ensure your function implementations exhibit the correct behavior. Imports No imports allowed on this assignment, with the following exceptions: $$ Any modules you have written yourself. $$ typing$-$ this is not required, but some students have requested it$.$ Submission Submit the following files to Gradescope: $$ simple$\_$tree$\_$functions.py $$ higher$\_$order$\_$tree$\_$functions.py Please note this assignment is $100\%$ manually graded. Students must submit individually by the due date $($Tuesday$,$ April $9$th at $11$:$59$ pm EST$)$ to receive credit.