# leetcode 98

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, -2147483648, 2147483647);
    }
    
    bool isValidBST(TreeNode* node, int lowerBound, int upperBound) {
        if (node == NULL) {
            return true;
        }
        
        int value = node->val;
        if (value < lowerBound || value > upperBound) {
            return false;
        }
        
        bool isLeftBST = false;
        if (value == -2147483648) {
            isLeftBST = node->left == NULL;    
        } else {
            isLeftBST = isValidBST(node->left, lowerBound, value - 1);
        }
        bool isRightBST = false;
        if (value == 2147483647) {
            isRightBST = node->right == NULL;    
        } else {
            isRightBST = isValidBST(node->right, value + 1, upperBound);
        }
        
        return isLeftBST && isRightBST;
    }
};