# 98. Validate Binary Search Tree

{% hint style="success" %}
We need a helper function to return each subtree's minimum and maximun values.
{% endhint %}

### Solution 1:

![](/files/-M7_GqVMD1jx2tg_Ya0r)

1. helper function - max and min value in a subtree
2. isValid function - both of left and right subtrees are valid, left\_max < root and right\_min > root, then it's valid.

{% tabs %}
{% tab title="Python" %}

```
// Some code
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = self.isBST(root)
        return res[2]
        
    def isBST(self, root):   # return a tuple: (minValue, maxValue, isValid)
        # ege case
        if root == None:
            return (float('inf'), float('-inf'), True)
        
        left = self.isBST(root.left)
        right = self.isBST(root.right)
        
        if root.val > left[1] and root.val < right[0] and left[2] and right[2]:
            isValid = True
        else:
            isValid = False
            
        minValue = min(min(left[0], right[0]), root.val)
        maxValue = max(max(left[1], right[1]), root.val)
        
        return (minValue, maxValue, isValid)
```

{% endtab %}

{% tab title="Java" %}

```java
final class TreeInfo {
    boolean isBST;
    long maxVal;
    long minVal;
    
    public TreeInfo(boolean isBST, long maxVal, long minVal) {
        this.isBST = isBST;
        this.maxVal = maxVal;
        this.minVal = minVal;
    }
}
class Solution {
    public boolean isValidBST(TreeNode root) {
        TreeInfo res = helper(root);
        return res.isBST;
    }
    
    public TreeInfo helper(TreeNode root) {
        if(root == null) return new TreeInfo(true, Long.MIN_VALUE, Long.MAX_VALUE);
        
        TreeInfo left = helper(root.left);
        TreeInfo right = helper(root.right);
        
        if(!left.isBST || !right.isBST) {
            return new TreeInfo(false, -1, -1);
        }
        
        if((root.val > left.maxVal) && (root.val < right.minVal))
            return new TreeInfo(true, Math.max(right.maxVal, root.val), Math.min(left.minVal, root.val));
        
        return new TreeInfo(false, -1, -1);
    }
}
```

{% endtab %}
{% endtabs %}

### Solution 2:

Compute inorder binary tree traversal, if whole list is ascending, then it's valid.

{% tabs %}
{% tab title="Java(iterative)" %}

```java
class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        Integer prev = null;
        
        while(!stack.isEmpty() || root != null) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(prev != null && root.val <= prev)
                return false;
            
            prev = root.val;
            root = root.right;
        }
        return true;
    }
}
```

{% endtab %}
{% endtabs %}

### Solution 3：

逆向思维，如果parent tree是BST，那么left sub tree的下限是左子树的low，上限是parent node.val. 那么right sub tree的下限是parent node.val，上限是右子树的up. 默认上限是无穷大，下限是无穷小。每个node遍历一遍，时间复杂度和空间度为 $$O(n)$$&#x20;

{% tabs %}
{% tab title="Python-iterative" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.isBSTChild(root)
    
    def isBSTChild(self, node, low = float('-inf'), upper = float('inf')):  #  -> list[max, min] 
        if node == None:
            return True
        
        if node.val <= low or node.val >= upper:
            return False
        
        if self.isBSTChild(node.left, low, node.val) == False or self.isBSTChild(node.right, node.val, upper) == False:
            return False
        
        return True
```

{% endtab %}

{% tab title="Python-recursive" %}

```python
class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
            
        stack = [(root, float('-inf'), float('inf')), ] 
        while stack:
            root, lower, upper = stack.pop()
            if not root:
                continue
            val = root.val
            if val <= lower or val >= upper:
                return False
            stack.append((root.right, val, upper))
            stack.append((root.left, lower, val))
        return True  
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/iii.-binary-tree/98.-validate-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.