> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/validate-binary-search-tree.md).

# 98. Validate Binary Search Tree

### Description

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.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/)
* [Leetcode](https://leetcode.com/problems/validate-binary-search-tree/)
* [ProgramCreek](https://www.programcreek.com/2012/12/leetcode-validate-binary-search-tree-java/)
* [YouTube](https://youtu.be/MILxfAbIhrE)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[2,1,3]

<div align="left"><img src="/files/-MFWvIsESuWX-56ndKIe" alt=""></div>

**Output:** true
{% endtab %}

{% tab title="Example 2" %}
**Input:** \[5, 1, 4, null, null, 3, 6]

<div align="left"><img src="/files/-MFWviAgFblSVG-FkjnQ" alt=""></div>

**Output:** false

**Explanation:** The root node's value is 5 but its right child's value is 4.
{% endtab %}
{% endtabs %}

### **Solutions**

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

```java
// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N) since we visit each node exactly once.
 * Space complexity : O(N) since we keep up to the entire tree.
 */

class Solution {
    LinkedList<TreeNode> stack = new LinkedList();
    LinkedList<Integer> uppers = new LinkedList();
    LinkedList<Integer> lowers = new LinkedList();

    public void update(TreeNode root, Integer lower, Integer upper) {
        stack.add(root);
        lowers.add(lower);
        uppers.add(upper);
    }

    public boolean isValidBST(TreeNode root) {
        Integer lower = null, upper = null, val;
        update(root, lower, upper);

        while (!stack.isEmpty()) {
            root = stack.poll();
            lower = lowers.poll();
            upper = uppers.poll();

            if (root == null) continue;
            val = root.val;
            
            if (lower != null && val <= lower) return false;
            if (upper != null && val >= upper) return false;
            
            update(root.right, val, upper);
            update(root.left, lower, val);
        }
        return true;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(N) since we visit each node exactly once.
 * Space complexity : O(N) since we keep up to the entire tree.
 */

public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    
    private boolean helper(TreeNode node, Integer lower, Integer upper) {
        if(node == null) return true;
        
        int val = node.val;
        
        if(lower != null && val <= lower) return false;
        
        if(upper != null && val >= upper) return false;
        
        return helper(node.left, lower, val) && 
                    helper(node.right, val, upper);
    }
}
```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : O(N) in the worst case when the tree is a BST or 
 *    the "bad" element is a rightmost leaf.
 * Space complexity : O(N) for the space on the run-time stack.
 */

class Solution {
    // We use Integer instead of int as it supports a null value.
    private Integer prev;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }

    private boolean inorder(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!inorder(root.left)) {
            return false;
        }
        if (prev != null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        return inorder(root.right);
    }
}
```

{% endtab %}

{% tab title="Solution 4" %}

```java
/**
 * Time complexity : O(N) in the worst case when the tree is BST or 
 *    the "bad" element is a rightmost leaf.
 * Space complexity : O(N) to keep stack.
 */
 
 class Solution {
    private Integer prev;
    
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        prev = null;
        return inorder(root);
    }
    
    private boolean inorder(TreeNode node) {
        Stack<TreeNode> stack = new Stack();
        TreeNode curr = node;
        
        while(!stack.isEmpty() || curr != null) {
            while(curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            
            if(prev != null && curr.val <= prev) {
                return false;
            }
            prev = curr.val;
            
            curr = curr.right;
        }
        return true;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*