Reading material

Additional material

Algorithm removeAll(key):
   Input: key
   Output: collection of elements of items in tree whose key is key
   Postcondition: items whose key is key have been removed from tree
collection empty collection
removeAll(key, root of tree, collection)
return collection

Algorithm removeAll(key, node, collection):
   Input: key; node of tree; collection of elements
   Postcondition: elements of items in subtree rooted at node whose key is key have been added to collection and those items have been removed from subtree rooted at node
if node is not a leaf then
     if key of node > key then
         removeAll(key, left child of node, collection)
     else if key of node < key then
         removeAll(key, right child of node, collection)
     else
         removeAll(key, right child of node, collection)
         element remove(key, node)
         add element to collection

Question