Count possible binary search trees

The goal of the algorithm is to count the number of correct binary search trees that could be created for a given list of continuous element (ie element between 1 and n)

2 solutions are proposed

The idea of the first solution is a reccurence:

1) Initialize the number of correct binary trees for 0 and 1 element (1 possible correct tree for each)

2) Use a reccurence with i, based on the fact that a binary tree will have x element on left subtrees and y on right subtrees with x+y=i and for x<i and y<i the number of correct subtrees are know

3) Compute for each x, y st x+y=i the number of subtrees as a product and store it for i

4) Increment until i=n and return the number of possible correct binary trees for n

# Solution 1
def numTrees(n: int) -> int:
    d = {0:1, 1:1} # initialization of the base cases
    
    # loop from 2 to n (n included)
    for i in range(2, n+1):
        curr = 0 # initialization of the number of tree for i element
        # check the number of correct binary trees for each j as pivot
        for j in range(i):
            curr += d[i-j-1] * d[j] # a given j will split the list of elements in two sublist with j element on one side and i-j-1 on the other side
        d[i] = curr # store the number of possible correct binary trees for i elements
    return(d[n])

The second algorithm will make a reccurence starting from n:

1) start with the list of n element and iterate over the values to choose as the current node

2) split the list of values in two sublists using the current node as pivot (smaller and greater)

3) compute recursively left and right number of possible subtrees by calling itself with respectively list of smaller elements and list of greater elements

4) The base case is when no element are left in the list and hence only a None Trees (ie 1 tree) can be created

# Solution 2
def numTrees(n: int) -> int:
    d = dict() # for memoization
    
    # helper will compute the number of possible trees with values between left and right
    def helper(left, right):
        # if the tuplet (left, right) is already in d, returned the stored value
        if (left, right) in d:
            return(d[(left, right)])

        if left > right:
            # if left > right the list of values to add is empty and only 1 None tree can be created
            d[(left, right)] = 1 # store the value
            return 1
        else:
            total_trees = 0
            # loop on i between left and right where i is the current node value
            for i in range(left, right+1):
                number_left_subtrees = helper(left, i-1) # number of possible correct subtrees on left branch
                number_right_subtrees = helper(i+1, right) # number of possible correct subtrees on right branch
                total_trees += number_left_subtrees * number_right_subtrees # add the number of correct subtrees with i a pivot
            d[(left, right)] = total_trees # store the value
            return(total_trees)
    return(helper(1, n))