Check if a binary tree is a binary search tree

Binary Search Tree는 아래 그림(Wikipedia에서 복사)에서 보는 것과 같이 root node의
왼쪽 Subtree는 root node의 값 8보다 적은 값들만,
오른쪽 Subtree는 root node의 값 8보다 큰 값들만 분포되도록 만들어진 Tree이다.

따라서, 주어진 Tree가 Binary Search Tree인지 아닌지 확인하기 위해서는, root node를 positive/negative infinite number와 비교하여 root node가 positive/negative infinite number 내에 존재하는지를 확인한다. 

만약, positive/negative infinite number 내에 존재하면, root node 의 값을 최대값으로 하여 왼쪽 subtree가 root node 값보다 작은 값으로 구성되어져 있는지 확인힌다.

마친가지로, 오른쪽 Subtree로 root node의 값을 최소값으로하여 오른쪽 Subtree의 값들이 root node 값보다 큰 값으로 구성되어져 있는지 확인한다. 왼쪽 Subtree와 오른쪽 Subtree를 확인한 값이 모두 참인 경우에 Binary Search Tree가 된다.

주의.  논란의 여지는 있지만, null tree인 경우에는 Binary Search Tree로 정의한다.

boolean isBST( node root, int MAX, int MIN ) {

    if( root==null )

        return true;

    if( MAX>root.getValue() && MIN < root.getValue() )

        return( isBST(root.getLeft(), MIN, root.getValue() )  && isBST(root.getRight(),root.getValue(), MAX ) );

    else

        return false;

    }

}