> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/tree/0098.-validate-binary-search-tree.md).

# 0098. Validate BST

Medium  |  Binary Search Tree + Recursion / Stack  |  28 ms (94.97%),  17.7 MB (95.43%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0098-validate-binary-search-tree)

Given the `root` 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.
  {% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in the tree is in the range `[1, 10^4]`.
* `-2^31 <= Node.val <= 2^31 - 1`
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title=" 💡 Ideas" %}
{% hint style="info" %}
Keep maintaining the **"Upper Bound" and "Lower Bound"** while visiting.
{% endhint %}

* For visiting the **left-child node**, we **update the upper bound** by the current node's value and keep the lower bound (*All child nodes in the left-subtree should not have values greater than their parent.*)
* For visiting the **right-child node**, we ***update the lower bound*** by the current node's value and keep the upper bound (*All child nodes in the right-subtree should not have values less than their parent.*)
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # (base case)
        if not root.left and not root.right: return True
        
        # ==================================================
        #  Tree + DFS + Stack                (Iterative)   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [(root, float('-inf'), float('inf'))]
        while stack:
            node, lower, upper = stack.pop()
            
            if node.val >= upper or node.val <= lower: return False
            
            # (left  sub-tree) set UPPER bound to current node's value (<= curValue)
            if node.left : stack.append( (node.left,  lower,    node.val) )
            
            # (right sub-tree) set LOWER bound to current node's value (>= curValue)
            if node.right: stack.append( (node.right, node.val, upper) )
                
        return True
    
    '''
    # ==================================================
    #  Tree + DFS + Stack                (Recursive)   =
    # ==================================================
    # time  : O(n)
    # space : O(n)

    def _isValidBSTHelper(self, node, lower, upper):
        if not node: return True

        if ((upper > node.val > lower)                              and
            self._isValidBSTHelper(node.left,  lower,    node.val ) and
            self._isValidBSTHelper(node.right, node.val, upper)):
            return True

        return False

    def isValidBST(self, root: TreeNode) -> bool:
        # (base case)
        if not root.left and not root.right: return True

        return self._isValidBSTHelper(root, float('-inf'), float('inf'))
    '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
     
    public boolean isValid(TreeNode node, long lower, long upper) {
        if(node == null) return true;
        
        return (lower < node.val && node.val < upper) &&
               isValid(node.left, lower, node.val)    && 
               isValid(node.right, node.val, upper);
    }
    
    public boolean isValidBST(TreeNode root) {
        if(root.left == null && root.right == null) return true;
        
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}
```

{% endtab %}
{% endtabs %}