# LC 98. Validate Binary Search Tree

### [Problem link](https://leetcode.com/problems/validate-binary-search-tree/)

###### tags: `leedcode` `medium` `c++` `BST`

Given the <code>root</code> of a binary tree, determine if it is a valid binary search tree (BST).

A **valid 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:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg" style="width: 302px; height: 182px;" />

Input: root = [2,1,3]
Output: true

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg" style="width: 422px; height: 292px;" />

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

**Constraints:**

- The number of nodes in the tree is in the range <code>[1, 10⁴]</code>.
- <code>-2³¹ <= Node.val <= 2³¹ - 1</code>

## Solution 1 - Recursion
#### C++

/**
 * 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 preorder(TreeNode *node, long long minVal, long long maxVal) {
        if (node == nullptr) {
            return true;
        }
        if (!(minVal < node->val && node->val < maxVal)) {
            return false;
        }
        return preorder(node->left, minVal, node->val) && preorder(node->right, node->val, maxVal);
    }

    long long pre = LLONG_MIN;
    bool inorder(TreeNode *node) {
        if (node == nullptr) {
            return true;
        }
        if (!inorder(node->left) || pre >= node->val) {
            return false;
        }
        pre = node->val;
        return inorder(node->right);
    }

    pair<long long, long long> postorder(TreeNode *node) {
        if (node == nullptr) {
            return {LLONG_MAX, LLONG_MIN};
        }
        auto [leftMin, leftMax] = postorder(node->left);
        auto [rightMin, rightMax] = postorder(node->right);
        long long val = node->val;
        if (!(leftMax < val && val < rightMin)) {
            return {LLONG_MIN, LLONG_MAX};
        }
        return {min(leftMin, val), max(rightMax, val)};
    }

    bool isValidBST(TreeNode* root) {
        // return preorder(root, LLONG_MIN, LLONG_MAX);
        // return inorder(root);
        // return postorder(root).first != LLONG_MIN;
        return postorder(root).second != LLONG_MAX;
    }
};

## Solution 2 - Iteration
#### C++

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        queue<tuple<TreeNode *, long long int, long long int>> q;
        q.push({root, LLONG_MIN, LLONG_MAX});

        while (!q.empty()) {
            auto [node, low, high] = q.front();
            q.pop();

            if (node == nullptr) {
                continue;
            }
            if (low < node->val && node->val < high) {
                q.push({node->left, low, node->val});
                q.push({node->right, node->val, high});
            } else {
                return false;
            }
        }
        return true;
    }
};

>### Complexity
> n = The number of nodes in the tree
> w = The maximum width of tree
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(n) |

## Note
sol1:
[Ref: 0x3F](https://www.bilibili.com/video/BV14G411P7C1/?p=11&spm_id_from=pageDriver)

inorder:
postorder: