Validate Binary Search Tree

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 strictly less than the node’s key.
• The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Intuition

Based on the BST definition, we could set min and max as the value’s boundary. The left subtree’s value must be strictly less than the root value, and vice versa for the right subtree (strictly greater).

Algorithm

class Solution {
public:
	bool isValidBST(TreeNode* root) {
		return isValid(root, LLONG_MIN, LLONG_MAX);
	}

	bool isValid(TreeNode* root,long long min, long long max){
		if(root == nullptr){
		return true;
		}
		
		if(root->val <= min){
		return false;
		}
		
		if(root->val >= max){
		return false;
		}
		
		return isValid(root->right, root->val, max) && isValid(root->left, min, root->val);
	}
};