Generate Binary Search Trees

The goal of the algorithm is to create every possible binary search trees for a given list of continuous element (ie element between 1 and n)

The idea of the algorithm is to:

1) iterate over values in the list 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) create recursively left and right list of possible subtrees by calling itself with respectively list of smaller elements and list of greater elements

def generateTrees(n: int) -> List[Optional[TreeNode]]:
    # helper will create a tree with values between left and right
    def helper(left, right):
        # if left > right the list of values to add is empty
        if left > right:
            return([None])
        else:
            # list_trees will contain all the possible trees given left and right
            list_trees = []
            # loop on i between left and right where i is the current node value
            for i in range(left, right+1):
                list_left_subtrees = helper(left, i-1) # list of left subtrees contain different combination of the values smaller than i
                list_right_subtrees = helper(i+1, right) # list of right subtrees contain different combination of the values greater than i

                # add all possible combinations of trees for i as node value
                for left_subtree in list_left_subtrees:
                    for right_subtree in list_right_subtrees:
                        list_trees.append(TreeNode(i, left_subtree, right_subtree))
            # returns list_trees: all the combinations for every i as node value
            return(list_trees)

    return(helper(1, n))