Decide if a Binary Tree is Binary Search Tree

Question:
Given a binary tree, validate if it's a binary search tree.

Analysis:
The elements in a BST are sorted if traversed in-order. This is a very important feature BST and based on the definition, the problem can be solved by in-order traversal.

The class definition of tree node:

Based on the analysis above, we can have the implementation below.

Many people may think we can simply check "left.value < parent.value < right.value" for each node. That being said, we can have an implementation like this:

However, this is not correct. Simply checking the parent and children relationship is not sufficient. Here is a counter-example.

      5
     /  \
    /    \
   3    7
  / \    / \
2  6  4  9

This is a top-down approach although it's not correct. If adding more constraints on the value for each node, there is a working solution for this. Here is the implementation: