python - Generate a random binary tree with n vertices

I am debugging an algorithms task, and for the purpose of testing I want to generate a binary tree with n vertices rooted at 0, in other words, generate a sequence of pairs so that if the i-th pair in the sequence is (a,b), then the left child of i-th node is a, and the right child is b, except when a (or b) = -1, then i-th node has no left (or right) child. (e. g. a sequence: (1, 2), (-1, -1), (-1, -1) is a tree with the root (0), and two children (1 and 2)) I wrote the following python recursive function, where listAdd is the desired pair list, listDel is all vertices not yet generated, and n is the node currently being looked at:

 
def generateTree(listAdd, listDel, n):
    if not listDel:
        return
    ifLeft = bool(randint(0,1))
    ifRight = bool(randint(0,1))
    if ifLeft:
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (chosen, listAdd[n][1])
        generateTree(listAdd, listDel, chosen)
    else:
        listAdd[n] = (-1, listAdd[n][1])
    if not listDel:
        return
    if ifRight:
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (listAdd[n][0], chosen)
        generateTree(listAdd, listDel, chosen)
    else:
        listAdd[n] = (listAdd[n][0], -1)

However, upon writing it, I noticed that this does not work correctly, as it is possible for the function to stop after just one vertex, if ifLeft and ifRight both come out as false.

So my question is, what is a good way to generate such a tree? I don't need it to be in python, as it's only for generating an input file, all I need is a good algorithm, or another method of representing the tree so that it's easier to generate and can be converted into the desired format.