如何用C++递归验证二叉树是否为二叉搜索树（BST）

我尝试用C++写递归函数判断二叉树是否为BST，一开始只比较每个节点和它的直接左右子节点，但这显然不够——深层节点可能因为祖先节点的限制违反BST规则。比如下面这棵树：

10
      \
      15
     /
      6

节点6比15小，但它在10的右子树里，所以这棵树不是BST。我知道递归时需要跟踪每个节点的有效取值范围，但不确定怎么设计辅助函数。当前的节点结构是：

template <typename T>
struct Node {
    T value;
    Node<T>* left;
    Node<T>* right;
};

辅助函数的核心参数 #

辅助函数需要包含三个关键参数：

• 当前正在检查的Node<T>*节点
• 该节点允许的最小值边界（可以用const T*或者C++17的std::optional<T>，因为根节点没有初始下界）
• 该节点允许的最大值边界（同理，根节点没有初始上界）

递归过程中的范围更新思路 #

• 递归检查当前节点的左子树时：左子树所有节点的值必须小于当前节点的值，因此把当前节点的值作为左子树的最大值边界，最小值边界保持和当前节点的最小值边界一致
• 递归检查当前节点的右子树时：右子树所有节点的值必须大于当前节点的值，因此把当前节点的值作为右子树的最小值边界，最大值边界保持和当前节点的最大值边界一致
• 每个节点自身需要满足：如果存在最小值边界，则节点值必须大于该边界；如果存在最大值边界，则节点值必须小于该边界

内容的提问来源于stack exchange，提问作者dot