(Reminder --

isBinaryTree(nil).
isBinaryTree(node(_,Left,Right)) :- isBinaryTree(Left), isBinaryTree(Right).


/*
 * Binary Tree
   A binary tree is either empty (a node with no value)
   or it is a node that contains a value and a left and right subtree.
 * We will represent a binary tree in Prolog as either
    node(V, Lt, Rt)
    nil
 * BST
   A "binary search tree" (BST) is
   a type of binary tree where the nodes are arranged in order: for each
   node, all elements in its left subtree are less-or-equal to the node
   (=<), and all the elements in its right subtree are greater than the
   node (>).
 * Watch out for the exact wording in the problems
   -- a "binary search tree" is different from a "binary tree".
*/


isBst(nil).


isBst(node(V,Lt,Rt)):- 
      Lt = node(LV,_LLt,_LRt),
      LV =< V,   
      isBst(Lt),
      Rt = node(RV,_RLt, _RRt),
      V < RV,   
      isBst(Rt).




isBst(node(_V,nil,nil)).


isBst(node(V,Lt,nil) ) :-
     Lt = node(LV,_LLt,_LRt),
     LV =< V, 
     isBst(Lt).

isBst(node(V,nil,Rt)):-
     Rt = node(RV,_RLt,_RRt), 
     V < RV, 
     isBst(Rt).
















%the above code is not correct why??





% is_bst is correct code for isBst

is_bst(T):- is_bst(T,_Min,_Max).

is_bst(node(Root,nil,nil),Root,Root).

is_bst(node(Root,Left,Right),LMin,RMax):-
                               is_bst(Left,LMin,LMax),
			       is_bst(Right,RMin,RMax),
			       LMax =< Root,
			       RMin > Root.

is_bst(node(Root,Left,nil),LMin,Root):-
                               is_bst(Left,LMin,LMax),
			       LMax =< Root.


is_bst(node(Root,nil,Right),Root,RMax):-
			       is_bst(Right,RMin,RMax),
			       RMin > Root.



%:- is_bst(node(5,node(3,nil,nil),nil)).
%:- is_bst(node(5,node(3,node(1,nil,nil),node(8,nil,nil)),node(7,nil,nil))). %fails



% Pretty Print of tree.  Show the tree "sideways"

show(Tree) :- write('Tree =' ), nl,nl, showH(Tree,0).

% Helper procedure for displaying tree.

showH(nil, _).  % Do not display nil trees.
showH(node(Value, L, R),Indent):-
    Ind2 is Indent + 2,  % Indentions of 2 for subtree
    showH(R, Ind2),      % Display right subtree
    tab(Indent), write(Value),nl, % display root value if this tree
    showH(L,Ind2).       % Display left subtree

%:- show(node(5, node(3, node(1, nil, nil), node(4, nil, nil)), node(7, nil, nil))).