title: python - Generate a random binary tree with n vertices
body: <p>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:</p>
  
  <pre> <code>
  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)
  </code></pre>
  
  <p>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.</p>
  
  <p>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.</p>