% Figure 9.7  Finding an item X in a binary dictionary.


% in( X, Tree): X in binary dictionary Tree

in( X, t( _, X, _) ).

in( X, t( Left, Root, _) )  :-
  gt( Root, X),                    % Root greater than X
  in( X, Left).                    % Search left subtree 

in( X, t( _, Root, Right) )  :-
  gt( X, Root),                    % X greater than Root
  in( X, Right).                   % Search right subtree

gt( X,Y) :- number(X), number(Y), X > Y, !.

% examples
test( D) :- in( 5,D), in( 3,D), in( 8,D). 

test1(D) :- in( 5,D), in(3,D),in(8,D),in(1,D),in(6,D).