Enumeration of random trees

I'm interested in recursive generation of trees in Python. For my eventual application, it's important that the trees be represented as a list of nodes (rather than say a dictionary, or an edge list, or some other format). Also, in my eventual application, each node of the tree will have between 0 and hundreds of children. In this skeleton code, the number of children for each node is generated randomly.

The trees generated have a parameter-defined maximum depth, but because even nodes not at the maximum depth might have no children, some leaves will be closer to the root than others.

I wrote this function for the task:

import random

def generate_random_tree(nodelist=[], idx=0, parent=None, depth=0, max_children=2, max_depth=2):
    """Build a list of nodes in a random tree up to a maximum depth.
        :param:    nodelist     list, the nodes in the tree; each node is a list with elements [idx, parent, depth]
        :param:    idx          int, the index of a node
        :param:    parent       int, the index of the node's parent
        :param:    depth        int, the distance of a node from the root
        :param:    max_children int, the maximum number of children a node can have
        :param:    max_depth    int, the maximum distance from the tree to the root"""
    if depth =0:
        # add a random number of children
        n = random.randint(0, max_children)
        nodelist.extend([[idx+i, parent, depth] for i in xrange(n)])  

        # for each new child, add new children
        [generate_random_tree(nodelist, len(nodelist), idx+i, depth+1, max_children, max_depth) for i in xrange(n)]

    elif depth == max_depth:
        # add a random number of leaves
        n = random.randint(0, max_children)
        nodelist.extend([[idx+i, parent, depth] for i in xrange(n)])  
        return

    else:  # this should never happen
        raise ValueError('Algorithm halted because depth > max_depth or depth < 0.')
        return

The function

This is really nicely written code! I do have a few small tips, and then I'll try to answer some of your small questions.

• I noticed from looking at your code, that you only use the random.randint function from the random module/library. Rather than importing the entire random module, you can just do from random import randint.

• In your else block at the very end of your function, you have a return after you raise an exception. Raising an exception will exit the program, so this return can be removed entirely.

• You also mention in a comment by the else block, that this will never happen. If it never happens, then why do you need it? It can be removed as well.

• I did find something odd about this function. Underneath the comment # for each new child, add new children you have an expression that's evaluated, but you don't return the value of the expression. Preferably, this line should be changed to return [ ... ].

• Finally, using len to find the new appropriate indices is really the only good option, right now. You can always do tree[len(tree) - 1].index() + 1, but that's horridly unclear. Just stick with len.

StackExchange Code Review Q#94906, answer score: 4