function tree = removeBadSplits(tree,type)
% Remove splits that contribute nothing to the tree.

%   Copyright 2017-2019 The MathWorks, Inc

if ~strcmp(tree.options.mergeleaves,'on')
    return
end
N = length(tree.nodes);
isleaf = (tree.var==0)';   % no split variable implies leaf node

if type=='c'
    nodeprob = tree.nodeprob;
    err = nodeprob.*tree.nodeerror(:);
    % if error and no cost
    wclassprob = tree.wmembership./sum(tree.wmembership,2);
    risk = nodeprob-max(wclassprob,[],2).*nodeprob;
    % if error and cost, comput lowest cost here
    if ~isempty(tree.options.cost)
        C = tree.options.cost;
        nodecost = (wclassprob.*nodeprob)*C;
        risk = min(nodecost,[],2);
    end
    thre=100*eps(class(err));
else
    risk = tree.risk;
    thre=100*eps(class(risk));
end

isleafprune = isleaf;
prunealpha = 0;
prunelevel = 1;
prunelist = zeros(1,N);

while any(~isleafprune)
    leafcount=zeros(1,N);
    leaves=find(isleafprune);
    levels=max(tree.depth);
    while levels>0
        levelnodes=tree.nodes(tree.depth==levels);
        leafcount(levelnodes(ismember(levelnodes,leaves)))=1;
        notleaf=levelnodes(~ismember(levelnodes,leaves));
        notleafl=tree.left(notleaf);
        notleafr=tree.right(notleaf);
        leafcount(notleaf)=leafcount(notleafl)+leafcount(notleafr);
        levels = levels-1;
    end
    riskbranch = risk;
    branchalpha = zeros(1,N);
    for i=N:-1:1
        if ~isleafprune(i)
            riskbranch(i)=riskbranch(tree.left(i))+riskbranch(tree.right(i));
            branchalpha(i)=(risk(i)-riskbranch(i))./(leafcount(i)-1);
        end
    end
    if prunelevel==1 && any(abs(branchalpha(~isleafprune))<thre)
        isleafprune(abs(branchalpha)<thre & ~isleafprune')=true;
        continue
    end
    minalpha = min(branchalpha(~branchalpha==0));
    prunealpha = [prunealpha,minalpha];
    toprune = find(abs(branchalpha-minalpha)<thre);
    while ~isempty(toprune)
        pnode=toprune(1);
        if ~isleafprune(pnode)
            prunelist(pnode)=prunelevel;
        end
        isleafprune(pnode)=true;
        toprune=toprune(2:end);
        if tree.left(pnode)==0
            continue
        else
            toprune=[toprune,tree.left(pnode),tree.right(pnode)];
        end
    end
    prunelevel = prunelevel+1;
end

isleaf = (tree.var==0)';
doprune = (~isleaf) & ((prunelist==0)');

% Remove splits that are useless
if any(doprune)
   tree = internal.stats.bigdata.removeBranches(tree,find(doprune),type);
end
end