btDel(E,bt(E,nil,nil),nil):-!.

% If only one of the node’s subtrees is non-empty.
btDel(E,bt(E,nil,R),R):- R\=nil, !.

btDel(E,bt(E,L,nil),L):- L\=nil, !.

%  If the deleted node has two non-empty subtrees, find the left-most node in the right subtree. 
% Use this node to replace the one that is to be deleted. And need to update the right subtree.
btDel(E,bt(E,L,R),bt(Y,L,R1)):-
	delMinRight(Y,R,R1).

btDel(E,bt(E1,L,R),bt(E1,L1,R)):-
	E<E1, btDel(E,L,L1).

btDel(E,bt(E1,L,R),bt(E1,L,R1)):-
	E>E1, btDel(E,R,R1).

%%%%%%%
delMinRight(Y,bt(Y,nil,R),R).

delMinRight(Y,bt(E1,L,R),bt(E1,L1,R)):-
	L \= nil,
	delMinRight(Y,L,L1). 
%%%%%%%