Eine mögliche Implementation wäre:

class KeyValTree(BinaryTree):
  """This class encapsulates a tree of key/value pairs.

  It's somewhat unfortunate that what we call value in the BinaryNode
  now is the key of the key value pair.  We compensate with a bit
  of name shuffling magic.

  Additional magic in here is that you can create an "empty" node that
  is filled in as soon as it should receive a key/value.  This is mainly
  useful for the root node.
  >>> d = KeyValTree()
  >>> d["bla"] = "foo"
  >>> d["drei"] = 3
  >>> d["aaa"] = 9
  >>> d["bla"]
  'foo'
  >>> d["bla"] = 10
  >>> d["bla"]
  10
  >>> print d
    9
  10
    3
  """
  def __init__(self, key=None, value=None):
    BinaryTree.__init__(self, key)
    self.nodeValue = value

  getKey = BinaryTree.getValue

  def getValue(self):
    return self.nodeValue

  def setValue(self, value):
    self.nodeValue = value

  def __cmp__(self, other):
    try:
      return cmp(self.getKey(), other.getKey())
    except AttributeError:
      return -1

  def insert(self, key, value):
    """inserts newNode into the tree in a position such that
    the property of being sorted is maintained.

    Unfortunately, we need to replicate some code from
    SortedTree -- this may be a hint that we need to refactor,
    now that we have the additional functionality.  It would
    be concivable to let SortedTree.insert take a Node as
    well (it would then have to replace the node in case of
    a perfect match to make things work here).
    """
    if self.getKey() is None:
      self.value = key
      self.setValue(value)
    if key<self.getKey():
      setMeth, getMeth = self.setLeft, self.getLeft
    elif key==self.getKey():
      self.setValue(value)
      return
    else:
      setMeth, getMeth = self.setRight, self.getRight
    if not getMeth() is None:
      self.getMeth().insert(key, value)
    else:
      setMeth(KeyValTree(key, value))

  __setitem__ = insert

  def retrieve(self, key):
    """returns a the value for key if present, raises KeyError otherwise
    """
    try:
      if self.getKey()>key:
        return self.getLeft().retrieve(key)
      elif key==self.getKey():
        return self.getValue()
      else:
        return self.getRight().retrieve(key)
    except AttributeError:
      raise KeyError(key)

  __getitem__ = retrieve
  iterkeys = BinaryTree.__iter__

  def itervalues(self):
    yield self.getValue()
    for child in [self.getLeft(), self.getRight()]:
      if child is not None:
        for val in child.itervalues():
          yield val

Beachtet, dass sowohl insert als auch retrieve eigentlich nichts mehr machen müssen, nachdem sie ihren rekursiven Aufruf abgesetzt haben (in insert könnte man das noch etwas deutlicher machen, in retrieve stört die Exception-Behandlung etwas, aber das soll hier nicht kümmern). Solche Funktionen heißen endrekursiv und können vom System potenziell erheblich effizienter bearbeitet werden als rekursive Funktionen ohne diese Eigenschaft. Mehr dazu in Programmieren II – Python ist das ohnehin egal.

Wenn ihr Lust habt, implementiert doch einfach noch weitere Methoden, die ihr von Dictionaries kennt: keys, values, items (prima zum Traversieren…), has_key, iterkeys usf.