% -*- prolog -*-

%%% tree_member(A, T) checks if A is a number in T,
%%% where T is a sorted binary tree representing a set of numbers.

%%% empty tree: nil
%%% here's a tree with the numbers 3,4,7:  b(4, b(3,nil,nil), b(7,nil,nil))

% tree_member(A, nil) :- NO IT IS NOT

tree_member(E, b(E, _, _)).
tree_member(E, b(B, L, _)) :- E<B, tree_member(E, L).
tree_member(E, b(B, _, R)) :- E>B, tree_member(E, R).

% tree_insert(E, T1, T2)   T2 is just list T1 but w/ E inserted.

tree_insert(E, b(E, L, R), b(E, L, R)).
tree_insert(E, nil, b(E, nil, nil)).
tree_insert(E, b(F, L0, R), b(F, L, R)) :- E<F, tree_insert(E, L0, L).
tree_insert(E, b(F, L, R0), b(F, L, R)) :- E>F, tree_insert(E, R0, R).

% tree_insert_list(L, Told, Tnew)   Tnew is Told with all the elements of
%  L inserted.

tree_insert_list([], T, T).

tree_insert_list([E|L], Told, Tnew) :-
	tree_insert(E, Told, T), tree_insert_list(L, T, Tnew).

% tree_insert_list([1,7,2,5,3,6,2,4,8], nil, T).
