이진검색트리(Binary Search Tree)는 왼쪽 자식들이 부모 노드값보다 작고, 오른쪽 자식들이 부모 노드보다 크며, 중복된 값을 허용하지 않는다. 이러한 성질을 이용하여 재귀호출을 하면서, 왼쪽 자식들의 최대를 부모노드로, 오른쪽 자식들의 최소를 부모노드로 다시 지정하면서 자식노드들의 범위를 체크한다.

public static bool IsBst(Node root)
{
    var minNode = root;
    while(minNode.Left != null)
    {
        minNode = minNode.Left;
    }

    var maxNode = root;
    while(maxNode.Right != null)
    {
        maxNode = maxNode.Right;
    }

    return IsBst(root, minNode.Key, maxNode.Key);
}

public static bool IsBst(Node node, int min, int max)
{
    if (node == null) return true;

    if (node.Key < min || node.Key > max)
    {
        return false;
    }

    return IsBst(node.Left, min, node.Key)   // Left노드의 최대는 현재노드
	    && IsBst(node.Right, node.Key, max); // Right노드의 최소는 현재노드
}