98. Validate Binary Search Tree

In first place, I made a mistake that I only recursively compare the parent with its left and right child. This is incorrect. Note for a BST, all the nodes left child subtree are less than the root and on the other hand, all the nodes in right child subtree are larger than the root. Therefore, when doing the recursive call, we need to compare the current node with a minimal node and a maximal node. For the left subtree, the maximal node is the current node and for the right subtree, the minimal node is the current node. Also, the recursive function follows inorder traversal.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    bool isValidBST(TreeNode* root) {  
13:      return helper(root, NULL, NULL);  
14:    }  
15:    bool helper(TreeNode *root, TreeNode *minNode, TreeNode *maxNode) {  
16:      if (root == NULL) return true;  
17:      if (minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val) {  
18:        return false;  
19:      }  
20:      return helper(root->left, minNode, root) && helper(root->right, root, maxNode);  
21:    }  
22:  };