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 &lt; max_depth and depth &gt;=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 &gt; max_depth or depth &lt; 0.')
        return


The function is used like this:

tree =[[0, None, 0]]  # the algorithm starts with a root node which has no parents and depth 0
random.seed(0)
generate_random_tree(nodelist=tree, idx=len(tree), parent=0, depth=1, max_children=3, max_depth=3)

[0, None, 0]
[1, 0, 1]
[2, 0, 1]
[3, 0, 1]
[4, 1, 2]
[5, 1, 2]
[6, 1, 2]
[7, 4, 3]
[8, 5, 3]
[9, 6, 3]
[10, 6, 3]
[11, 2, 2]
[12, 11, 3]
[13, 11, 3]
[14, 11, 3]
[15, 3, 2]
[16, 15, 3]


This function does the task, but I'm eager for feedback on the quality of this implementation.  Any feedback is welcome, of course, but particular questions I have include:


Are there any better ways to find appropriate indices for each new node other than calling len()?
Are there simple, recursive Python implementations that return values rather than relying on list mutability? 
(This may be out of scope for se.cr; if so, please ignore)  Is there a way to get the enumeration to be depth-first rather than the breadth-first implementation I currently have?


Although this code isn't going to go into a production in environment or be worked on by teams of professional software engineers, high-level comments about readability, best practices, and hidden corner cases would be much appreciated.
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.