python - Generate a random binary tree with n vertices

user_3104621 0
Viewed 5639

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.

binary-tree random python
2 Answers

A simple iterative approach:

import random

# start with root node and no children
tree = [[-1, -1]]
free_edges = [(0, 0), (0, 1)]

n = 4  # how many nodes do you want?

while len(tree) < n:
    e = random.choice(free_edges)  # select a free edge
    node, child = e
    assert tree[node][child] == -1  # make sure we made no mistake

    k = len(tree)  # index of new node
    tree.append([-1, -1])  # add new node

    tree[node][child] = k  # set new node as child of an old node
    free_edges.extend([(k, 0), (k, 1)])  # new node has two free edges

    free_edges.remove(e)  # edge is no longer free

print(tree)
# [[1, 2], [-1, 3], [-1, -1], [-1, -1]]

Randomly insert new nodes into the tree until the total number of nodes is reached.

enter image description here The free edges are indicated in red. At each step, one free edge is chosen at random. A node is placed at that edge and this node adds two new free edges to the tree.

This procedure does not generate a specific order of nodes. Either the left child or the right child may be inserted into the tree first. I.e. you may get a sequence like [(2, 1), (-1, -1), (-1, -1)]. If this is a problem re-ordering of the nodes may be necessary.

I think this method will on average tend to produce more balanced trees than imbalanced trees because older edges are be considered more often. You may choose not to insert a new node and only remove the free edge with a certain probability. This should shift the tendency towards deeper trees. Just make sure not to remove all edges before being finished :)

user_30051670

You must not get a double zero when you're on the right end of your tree while still having some free elements, is that correct?

So I think you need to determine when this happens, AND force a recheck. There are 2 approaches that I can think of.

  • Make a function that checks where you are if you give it the root.

  • Create an array and populate it with 0,1 or "L","R". If you have

    • ifLeft == ifRight == 0
    • len(listDel) > 0 And
    • Checking the array, either:
      • If "L" not in check_array
      • if len(check_array) == sum(check_array)

Re-load the whole thing.

And by the way, you have to add the check to your array at the beginning of your function and remove it at the end. So its length will be like this:

0, 1, 2, 3, 4, 3, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 2, 1, 0

check_array = []

def generateTree(listAdd, listDel, n):
    if not listDel:
        return
    ifLeft = bool(randint(0,1))
    ifRight = bool(randint(0,1))

    if (ifLeft + ifRight == 0) and (
        "L" not in checked_array) and (
        len(listDel) > 0):
        // Force a 1, or use randint (you need a while-loop for it)
        ifLeft = 1

    if ifLeft:
        check_array.push("L")
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (chosen, listAdd[n][1])
        generateTree(listAdd, listDel, chosen)
        check_array = check_array[:-1]
    else:
        listAdd[n] = (-1, listAdd[n][1])
    if not listDel:
        return
    if ifRight:
        check_array.push("R")
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (listAdd[n][0], chosen)
        generateTree(listAdd, listDel, chosen)
        check_array = check_array[:-1]
    else:
        listAdd[n] = (listAdd[n][0], -1)
user_14340750
Related