# Validate Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/validate-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/validate-binary-search-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [IBM](https://scaleengineer.com/companies/ibm), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [SIG](https://scaleengineer.com/companies/sig)
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/validate-binary-search-tree/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/validate-binary-search-tree/image1.jpg) 

**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 `[1, 104]`.
* `-231 <= Node.val <= 231 - 1`

# Approaches
## Brute Force Recursion
This approach directly translates the definition of a Binary Search Tree into a recursive algorithm. For each node, it verifies that all nodes in its left subtree are smaller and all nodes in its right subtree are larger. It then recursively performs the same validation for the left and right children. This method is straightforward but highly inefficient.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Simple to understand and implement as it directly follows the definition of a BST.
**Cons:** Extremely inefficient due to redundant computations. The same subtrees are traversed multiple times.; Time complexity is poor, making it impractical for large trees.
### Explanation
The algorithm works by defining a function `isValidBST(node)` that checks if the subtree rooted at `node` is a valid BST. For this to be true, three properties must hold: the values in the left subtree must all be less than `node.val`, the values in the right subtree must all be greater than `node.val`, and both the left and right subtrees must also be valid BSTs. This leads to a recursive solution where for each node, we traverse its entire left and right subtrees to check the value constraints, and then make recursive calls on its children. The repeated traversals of the same nodes make this approach very slow.

```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;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // Check if all nodes in left subtree are less than root's value
        // and all nodes in right subtree are greater than root's value.
        // Then, recursively validate the left and right subtrees.
        return isSubtreeLessThan(root.left, root.val) &&
               isSubtreeGreaterThan(root.right, root.val) &&
               isValidBST(root.left) &&
               isValidBST(root.right);
    }

    // Helper to check if all nodes in a subtree are less than a given value.
    private boolean isSubtreeLessThan(TreeNode node, int value) {
        if (node == null) {
            return true;
        }
        return node.val < value &&
               isSubtreeLessThan(node.left, value) &&
               isSubtreeLessThan(node.right, value);
    }

    // Helper to check if all nodes in a subtree are greater than a given value.
    private boolean isSubtreeGreaterThan(TreeNode node, int value) {
        if (node == null) {
            return true;
        }
        return node.val > value &&
               isSubtreeGreaterThan(node.left, value) &&
               isSubtreeGreaterThan(node.right, value);
    }
}
```
### Algorithm
- The main function `isValidBST(root)` serves as the entry point.
- If the `root` is `null`, the tree is trivially valid, so return `true`.
- The core logic is to check three conditions for the current `root`:
  1. All nodes in the left subtree must have values strictly less than `root.val`. This is checked by a helper function, e.g., `isSubtreeLessThan(root.left, root.val)`.
  2. All nodes in the right subtree must have values strictly greater than `root.val`. This is checked by another helper, e.g., `isSubtreeGreaterThan(root.right, root.val)`.
  3. Both the left and right subtrees must themselves be valid binary search trees. This is checked by recursively calling `isValidBST(root.left)` and `isValidBST(root.right)`.
- The function returns `true` only if all three conditions are met for every node in the tree.

## Recursive Traversal with Valid Range
A much more efficient approach is to perform a single top-down traversal. Instead of re-validating subtrees, we pass down the valid range of values (lower and upper bounds) that each node must fall into. The root can be any value, but as we descend, the constraints become tighter.
**Time:** O(N) · **Space:** O(H)
**Pros:** Optimal time complexity of O(N) as it visits each node only once.; Conceptually clean and directly enforces the global BST property at each node.
**Cons:** For very deep or skewed trees, the recursion depth can become very large, potentially leading to a `StackOverflowError`.
### Explanation
This approach avoids redundant work by keeping track of the valid value range for each node. The root node can have any value, so its range is effectively `(-∞, +∞)`. When we move to a left child of a node `p`, we know its value must be less than `p.val`. So, the valid range for the left child becomes `(parent's lower bound, p.val)`. Similarly, when we move to a right child, its value must be greater than `p.val`, so its range becomes `(p.val, parent's upper bound)`. We traverse the tree once, and at each node, we check if its value is within the allowed range. If any node violates its range, the tree is not a valid BST.

To handle the full range of integer values, including `Integer.MIN_VALUE` and `Integer.MAX_VALUE`, we can use `Integer` wrapper objects for the bounds, where `null` represents infinity.

```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;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        // Use null to represent negative and positive infinity.
        return validate(root, null, null);
    }

    private boolean validate(TreeNode node, Integer low, Integer high) {
        // An empty tree is a valid BST.
        if (node == null) {
            return true;
        }

        // The current node's value must be within the bounds.
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
            return false;
        }

        // Recursively check the left and right subtrees with updated bounds.
        return validate(node.left, low, node.val) && 
               validate(node.right, node.val, high);
    }
}
```
### Algorithm
- Define a recursive helper function `validate(node, low, high)`.
- The initial call from the main function will be `validate(root, null, null)`, where `null` for `low` and `high` represents negative and positive infinity, respectively.
- In the `validate` function:
  1. If `node` is `null`, it's a valid empty subtree, return `true`.
  2. Check if the current node's value violates the bounds. If `low` is not `null` and `node.val <= low`, or if `high` is not `null` and `node.val >= high`, return `false`.
  3. Recursively call `validate` for the left child, updating the upper bound to the current node's value: `validate(node.left, low, node.val)`.
  4. Recursively call `validate` for the right child, updating the lower bound to the current node's value: `validate(node.right, node.val, high)`.
  5. Return `true` only if both recursive calls return `true`.

## Iterative In-order Traversal
This approach is based on a key property of BSTs: an in-order traversal (Left-Root-Right) visits the nodes in non-decreasing order. For a valid BST, this order must be strictly increasing. We can perform an in-order traversal and check if each node's value is strictly greater than the previously visited node's value. An iterative implementation using a stack is efficient and avoids recursion depth issues.
**Time:** O(N) · **Space:** O(H)
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(H).; The iterative approach is robust and avoids potential stack overflow errors on skewed trees.
**Cons:** The logic can be slightly less intuitive to grasp compared to the direct recursive validation.
### Explanation
Instead of passing value ranges down the tree (top-down), we can verify the BST property by checking the node order during an in-order traversal (bottom-up, in a sense). The in-order traversal visits the leftmost node first, then its parent, then the parent's right child's subtree. By keeping track of the value of the previously visited node, we can ensure that the current node's value is always greater. If we ever find a node whose value is less than or equal to the previous node's value, we have found a violation of the BST property.

The iterative approach uses an explicit stack to simulate the recursion of an in-order traversal. This makes the solution robust against stack overflow errors that can occur with deep, unbalanced trees.

```java
import java.util.Stack;

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        Integer prev = null; // Use Integer wrapper to handle the first element

        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            // Go to the leftmost node
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            
            // Visit the node at the top of the stack
            current = stack.pop();
            
            // Check if the inorder property is violated
            if (prev != null && current.val <= prev) {
                return false;
            }
            prev = current.val;
            
            // Move to the right subtree
            current = current.right;
        }
        return true;
    }
}
```
### Algorithm
- Initialize an empty `Stack` to aid the traversal and a variable `prev` (e.g., a nullable `Integer`) to `null`.
- Initialize a `current` pointer to the `root`.
- Start a loop that continues as long as `current` is not `null` or the `stack` is not empty.
  1. While `current` is not `null`, push it onto the `stack` and move to its left child (`current = current.left`). This finds the next node in the in-order sequence.
  2. Once `current` is `null`, pop a node from the `stack`. This is the current node to be processed.
  3. Check the BST property: If `prev` is not `null` and the popped node's value is less than or equal to `prev`, the order is violated. Return `false`.
  4. Update `prev` with the current node's value.
  5. Move to the right child of the popped node (`current = node.right`) to continue the traversal.
- If the loop completes without returning `false`, the entire tree has been traversed in sorted order. Return `true`.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private TreeNode prev ; public bool IsValidBST ( TreeNode root ) { prev = null ; return dfs ( root ); } private bool dfs ( TreeNode root ) { if ( root == null ) { return true ; } if (! dfs ( root . left )) { return false ; } if ( prev != null && prev . val >= root . val ) { return false ; } prev = root ; if (! dfs ( root . right )) { return false ; } return true ; } }
```

### Java

```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; * } * } */ class Solution { private Integer prev ; public boolean isValidBST ( TreeNode root ) { prev = null ; return dfs ( root ); } private boolean dfs ( TreeNode root ) { if ( root == null ) { return true ; } if (! dfs ( root . left )) { return false ; } if ( prev != null && prev >= root . val ) { return false ; } prev = root . val ; if (! dfs ( root . right )) { return false ; } return true ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST =
  function (root) {
    let prev = null;
    let dfs = function (root) {
      if (!root) {
        return true;
      }
      if (!dfs(root.left)) {
        return false;
      }
      if (prev && prev.val >= root.val) {
        return false;
      }
      prev = root;
      if (!dfs(root.right)) {
        return false;
      }
      return true;
    };
    return dfs(root);
  };

```

### CPP

```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: TreeNode * prev ; bool isValidBST ( TreeNode * root ) { prev = nullptr ; return dfs ( root ); } bool dfs ( TreeNode * root ) { if ( ! root ) return true ; if ( ! dfs ( root -> left )) return false ; if ( prev && prev -> val >= root -> val ) return false ; prev = root ; if ( ! dfs ( root -> right )) return false ; return true ; } };
```

### Python

```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 # 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 : # recursive def isValidBST ( self , root : Optional [ TreeNode ]) -> bool : def dfs ( root , mi , ma ): if not root : return True return mi < root . val < ma and dfs ( root . left , mi , root . val ) and dfs ( root . right , root . val , ma ) return dfs ( root , - math . inf , math . inf ) class Solution : # iterative def isValidBST ( self , root : TreeNode ) -> bool : # store (node, lower, upper) tuples in a single queue queue = [( root , None , None )] # another option: # queue = [(root, -math.inf, math.inf)] while queue : node , lower , upper = queue . pop ( 0 ) if node is None : continue val = node . val if lower is not None and val <= lower : return False if upper is not None and val >= upper : return False queue . append (( node . right , val , upper )) queue . append (( node . left , lower , val )) return True ############ class Solution : def isValidBST ( self , root : Optional [ TreeNode ]) -> bool : def isValidBST ( root : Optional [ TreeNode ], minNode : Optional [ TreeNode ], maxNode : Optional [ TreeNode ]) -> bool : if not root : return True if minNode and root . val <= minNode . val : return False if maxNode and root . val >= maxNode . val : return False return isValidBST ( root . left , minNode , root ) and isValidBST ( root . right , root , maxNode ) return isValidBST ( root , None , None ) ############ # 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 : def dfs ( root ): nonlocal prev if root is None : return True if not dfs ( root . left ): return False if prev >= root . val : return False prev = root . val if not dfs ( root . right ): return False return True prev = - inf return dfs ( root ) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def isValidBST ( self , root ): """ :type root: TreeNode :rtype: bool """ prev = - float ( "inf" ) stack = [( 1 , root )] while stack : p = stack . pop () if not p [ 1 ]: continue if p [ 0 ] == 0 : if p [ 1 ]. val <= prev : return False prev = p [ 1 ]. val else : stack . append (( 1 , p [ 1 ]. right )) stack . append (( 0 , p [ 1 ])) stack . append (( 1 , p [ 1 ]. left )) return True
```