---
# System prepended metadata

title: LC 98. Validate Binary Search Tree
tags: [medium, leedcode, BST, c++]

---

# 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<sup>4</sup>]</code>.
- <code>-2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1</code>

## Solution 1 - Recursion
#### C++
```cpp=
/**
 * 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++
```cpp=
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:
![image](https://hackmd.io/_uploads/SkByfZ4L0.png)
postorder:
![image](https://hackmd.io/_uploads/BkeTZbELR.png)
