Reading material

Additional material

public Object findElement(Object key) {
    return findElement(key, tree.root());
}
private Object findElement(Object key, Position position) {
    if (position is leaf) {
        if (key is equal to key of position) {
            return element of position;
        } else {
            return NO_SUCH_KEY;
        }
    } else if (key is less than key of position) {
        if (position has left child) {
            findElement(key, left child of position);
        } else {
            return NO_SUCH_KEY;
        }
    } else if (key is greater than key of position) {
        if (position has right child) {
            findElement(key, right child of position);
        } else {
           return NO_SUCH_KEY;
        }
    } else { // key is equal to key of position
        return element of position;
        
    }
}
public void insertItem(Object key, Object element) {
    insertItem(key, element, tree.root());
}
private void insertItem(Object key, Object element, Position position) {
    if (position is leaf) {
        if (key is less than key of position) {
            add a node with new Item(key, element) as its element as left child of position;
        } else {
            add a node with new Item(key, element) as its element as right child of position;
        }
    } else if (key is less than key of position) {
        if (position has left child) {
            insertItem(key, element, left child of position);
        } else { 
            add a node with new Item(key, element) as its element as left child of position;
        }
    } else { // key is greater than or equal to key of position
        if (position has right child) {
            insertItem(key, element, right child of position);
        } else { 
            add a node with new Item(key, element) as its element as right child of position;
        }
    }
}
public Object remove(Object key) {
    remove(key, tree.root());
}
private Object remove(Object key, Position position) {
    if (position is leaf) {
        if (key is equal to key of position) {
            remove position;
            return element of position;
        } else {
            return NO_SUCH_KEY;
        }
    } else if (key is less than key of position) {
        if (position has left child) {
            remove(key, left child of position);
        } else {
            return NO_SUCH_KEY;
        }
    } else if (key is greater than key of position) {
        if (position has right child) {
            remove(key, right child of position);
        } else {
           return NO_SUCH_KEY;
        }
    } else { // key is equal to key of position
        replace element of position by removeMin(right child of position); 
        return old element of position;       
    }
}
private Object removeMin(Position position) {
    if (position is leaf) {
        remove position;
        return element of position;
    } else if (position has no left child) {
        replace position by right child;
        return old element of position;
    } else { // position has left child
        removeMin(left child of position);
    }
}