1
// We know inorder traversal of BST is always sorted, so we are just finding
2
// inorder traversal and check whether it is in sorted manner or not, but only
3
// using const space using prev pointer.
4
class Solution {
5
 public:
6
  TreeNode *prev;
7
  Solution() {
8
    prev = NULL;
9
  }
10
  bool isValidBST(TreeNode *root) {
11
    if (root == NULL) return true;
12
    bool a = isValidBST(root->left);
13
    if (!a) return false;
14
    if (prev != NULL) {
15
      if (prev->val >= root->val) return false;
16
    }
17
    prev = root;
18
    return isValidBST(root->right);
19
  }
20
};