Q: sort's key and cmp parameters

[Paul Rubin]

Raymond Hettinger <python at rcn.com> writes:
> Can you give an example of a list of trees and a cmp function
> that recursively compares them?

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', ...}},
                    ...
                   ]

Example comparison function:

  def compare(tree1, tree2):
     c = cmp(tree1['value'], tree2['value'])
     if c != 0: return c
     c = cmp(tree1['left'], tree2['left'])
     if c != 0: return c
     return cmp(tree1['right'], tree2['right])

> 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.

> From the sound of it, the trees are static during the sort and
> would get a nice O(n log n) --> O(n) speed-up if a key function
> were allowed to flatten them in a single pass.

But the key function has to do all those comparisons on the internal
nodes.