function out = delete(t, x)
% delete x from t
if isempty(t) 
    out = {};
elseif t.key > x
    t.left = delete(t.left, x);
    out = t;
elseif t.key < x
    t.right = delete(t.right, x);
    out = t;
else % t.key == x
    if isempty(t.left)
        out = t.right;
    elseif isempty(t.right)
        out = t.left;
    else % both children non-empty
        [t.left, mkey] = deletemin(t.left);
        t.key = mkey;
        out = t;
    end;
end;