A fictional forest trail starts from a given point START. At the start or at further named points the path can fork into a left path and a right path. At any point there can be a left path only or a right path only. The trail can be represented by a rooted binary tree, such as:

For this example, the trail ends at the leaves of the tree, that is, D, E, F and G.

Given a trail represented by a rooted tree, trail, write a recursive function called ends that calculates the number of points at which a trail ends. For the example above, this would return 4.

Test your function by running the test code given below. If any tests fail, then debug your function, and run the test code again. You can repeat this iterative process as many times as you want. If there are any tests that fail and you are unable to identify the problem, you may add explanatory comments below the test code.

# Compute the number of trail ends in trail # Write your recursive function here

# Test code EMPTY = Tree() F = join('F',EMPTY,EMPTY) G = join('G',EMPTY,EMPTY) C = join('C',F,G) D = join('D', EMPTY,EMPTY) A = join('A',C,D) E = join('E',EMPTY,EMPTY) B = join('B',E,EMPTY) START = join('START',A,B)

trail_tests = [ # case, trail, number of trail ends ('empty tree', EMPTY, 0), ('no subtrees, already trail end', F, 1), ('one subtree, trail end', B, 1), ('two subtrees, neither subtree is a trail end', START, 4), ('two subtrees, one subtree is a trail end', A, 3), ('two subtrees, both subtrees are trail ends', C, 2) ] test(ends, trail_tests) # Add any explanatory comments here

START