# 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

# Solution

Approach 1: Check that the inorder traversal is monotonically increasing.

Approach 2: Intuitive recursion -- each node in the tree should be bounded by a upper and lower bound given their parents in a BST. Check if each node is in bound.

# Code (Python)

Approach 1:

    def isValidBST(self, root: 'TreeNode') -> 'bool':
        # inorder traversal is increasing
        if not root:
            return True
        stack = []
        node = root
        while node:
            stack.append(node)
            node = node.left
        prev = None
        while stack:
            node = stack.pop()
            if prev and prev.val >= node.val:
                return False
            prev = node
            node = node.right
            while node:
                stack.append(node)
                node = node.left
        return True

Approach 2:

    def isValidBST(self, root: 'TreeNode') -> 'bool':
        # recursive with boundaries
        return self._helper(root, -float('inf'), float('inf'))
    
    def _helper(self, node, lo, hi):
        if not node:
            return True
        if not lo < node.val < hi:
            return False
        return self._helper(node.left, lo, node.val) and self._helper(node.right, node.val, hi)
            

# Code (C++)

Approach 1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// Inorder traversal.
// Recursion.
class Solution {
private:
    TreeNode *prev = NULL;;
public:
    bool isValidBST(TreeNode* root) {
        if (root == NULL)
            return true;
        if (!isValidBST(root->left))
            return false;
        if (prev && prev->val >= root->val)
            return false;
        prev = root;
        return isValidBST(root->right);
    }
};
// Iteration.
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode *curr = root;
        TreeNode *prev = NULL;
        while (curr || !st.empty())
        {
            if (curr)
            {
                st.push(curr);
                curr = curr->left;
            }
            else
            {
                curr = st.top();
                st.pop();
                if (prev && prev->val >= curr->val)
                    return false;
                prev = curr;
                curr = curr->right;
            }
        }
        return true;
    }
};

Approach 2:

// Intuitive recursion.
class Solution {
private:
    bool checkIsValidBST(TreeNode *root, int *min, int *max) {
        int leftMin = root->val;
        int leftMax = root->val;
        int rightMin = root->val;
        int rightMax = root->val;
        if (root->left && 
            (!checkIsValidBST(root->left, &leftMin, &leftMax) ||
             root->val <= leftMax))
            return false;
        if (root->right &&
            (!checkIsValidBST(root->right, &rightMin, &rightMax) ||
             root->val >= rightMin))
            return false;
        if (min) *min = leftMin;
        if (max) *max = rightMax;
        return true;
    }
public:
    bool isValidBST(TreeNode* root) {
        if (root == NULL)
            return true;
        return checkIsValidBST(root, NULL, NULL);
    }
};