3. [12] The function num.trees takes the total number of nodes and the number of leaves, and returns the number of AVI-balanced tree shapes with that many nodes and leaves Here is a sample call of num_trees: >>>num_trees (5, 3) 2 This means that there are exactly two AVL-balanced trees that have five nodes where three of those nodes are leaves. Here are those two trees: Implement num_trees. Note: we're not asking you to implement any optimizations. As such, this thing really slows down when the number of nodes increases. We hope that your code can solve cases with 8 nodes or fewer in under a minute. It should of course be correct for larger numbers of nodes too, but it's OK if the time taken in these cases is prohibitive. (We're happy to talk to you about several possible optimizations if you're interested!) Requirements . Your code must be written in Python 3, and the filename must be num-trees. py. We will grade only the num_trees function; please do not change its signature in the starter code. include as many helper functions as you wish Write-up: in your ps2.pdf/ps2.tex files, include an explanation of how your code works. Please include a formal proof of correctness 3. [12] The function num.trees takes the total number of nodes and the number of leaves, and returns the number of AVI-balanced tree shapes with that many nodes and leaves Here is a sample call of num_trees: >>>num_trees (5, 3) 2 This means that there are exactly two AVL-balanced trees that have five nodes where three of those nodes are leaves. Here are those two trees: Implement num_trees. Note: we're not asking you to implement any optimizations. As such, this thing really slows down when the number of nodes increases. We hope that your code can solve cases with 8 nodes or fewer in under a minute. It should of course be correct for larger numbers of nodes too, but it's OK if the time taken in these cases is prohibitive. (We're happy to talk to you about several possible optimizations if you're interested!) Requirements . Your code must be written in Python 3, and the filename must be num-trees. py. We will grade only the num_trees function; please do not change its signature in the starter code. include as many helper functions as you wish Write-up: in your ps2.pdf/ps2.tex files, include an explanation of how your code works. Please include a formal proof of correctness