[Paul Rubin] > Example of list of trees (nested dicts). In practice you could get > such a list from the simplejson module: > > list_of_trees = [{'value':1, 'left':{'value':3,'left':None,'right':None}, > 'right':{'value':7,'left':{'value':5, ...}}}, > {'value':19, 'left':{'value':23', ...}}, > ... > ]
So, it looks like the relevant comparison values can be stored in nested lists: list_of_lists = \ [[1, [3, [], []], [7, [5, [], []], []]], [19, [23, [], []], []], ] Here I've used a transformation where a tree is stored as: [tree['value'], tree['left'], tree['right']] and the None value indicating an empty tree transformed to: [] > > Example comparison function: > > def compare(tree1, tree2): > c = cmp(tree1['value'], tree2['value']) > if c != 0: return c > c = compare(tree1['left'], tree2['left']) > if c != 0: return c > return compare(tree1['right'], tree2['right]) Hmm, that recursive comparison order looks like how Python already recursively compares lists. So, perhaps the lists can be compared directly: if list_of_lists[0] < list_of_lists[1]: ... >> Are the trees user defined classes? > > Not in general. They might be nested tuples, lists, or dictionaries. > Or they could come from a non-extensible library-defined class, like > from cElementTree Are there any of these trees that cannot be transformed (by a key function) into an equivalent nested list of lists and values so that the trees can be directly compared to one another using Python's normal built-in recursive comparison order for lists? Raymond -- http://mail.python.org/mailman/listinfo/python-list