# Validate Binary Search Tree

Published: Jan 16, 2023

Medium Binary Search Tree Depth-First Search

## Problem Description

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.

Constraints: The number of nodes in the tree is in the range `[1, 10**4]`.

• `-2**31 <= Node.val <= 2**31 - 1`

https://leetcode.com/problems/validate-binary-search-tree/

## Examples

``````Example 1
Input: root = [2,1,3]
Output: true
Explanation:
2
/   \
1      3
``````
``````Example 2
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.
5
/   \
1      4
/   \
3     6
``````

## How to Solve

Check each node value is less than upper bound and greater than lower bound. Start from a minimum value as a lower bound and a maximum value as a upper bound. The solution here took depth-first search (recursive). When it goes to a left subtree, lower bound is from previous one and upper bound is a parent node value. When it goes to a right subtree, lower bound is a parent node value and upper bound is from previous one. If all node values are valid, the tree is a valid BST.

## Solution

``````/**
* 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 ValidateBinarySearchTree {
private:
bool helper(TreeNode* root, long long low, long long high)
{
if (!root)
return true;
if (root->val <= low || root->val >= high)
return false;
return helper(root->left, low, root->val) && helper(root->right, root->val, high);
}
public:
bool isValidBST(TreeNode* root) {
return helper(root, LLONG_MIN, LLONG_MAX);
}
};
``````
``````
``````
``````
``````
``````# 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 ValidateBinarySearchTree:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def helper(root: Optional[TreeNode], low, high)-> bool:
if not root:
return True
if root.val <= low or root.val >= high:
return False
return helper(root.left, low, root.val) and\
helper(root.right, root.val, high)

return helper(root, float('-inf'), float('inf'))
``````
``````# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
def helper(root, low, high)
if !root
return true
end
if root.val <= low || high <= root.val
return false
end
return helper(root.left, low, root.val) && helper(root.right, root.val, high)
end

# @param {TreeNode} root
# @return {Boolean}
def is_valid_bst(root)
return helper(root, -2**31-1, 2**31)
end
``````

## Complexities

• Time: `O(n)`
• Space: `O(h)` – h: height of the tree