Reading material

Additional material

Proposition 7.2 in PostScript and PDF
Total order in PostScript and PDF

findElement(key)
in: key to be searched for
out: element of item with key in dictionary; NO_SUCH_KEY if no such item exists
if tree is empty
    return NO_SUCH_KEY
else
    return findElement(key, root of tree)

findElement(key, node)
in: key to be searched for; root of subtree to be searched
out: element of item with key in subtree rooted at node; NO_SUCH_KEY if no such item exists
if node is leaf
    if key of node = key
        return element of node
    else
        return NO_SUCH_KEY
else if key of node = key
        return element of node
    else if key of node > key
        if node has left child
            return findElement(key, left child of node)
        else 
            return NO_SUCH_KEY
    else /* key of node < key */
        if node has right child
            return findElement(key, right child of node)
        else 
            return NO_SUCH_KEY