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.

Example 1:

Input: root = [2,1,3] 

Output: true 

Approach

Java

public class ValidateBST {
    public static void main(String[] args) {

        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        long min = Long.MIN_VALUE;
        long max = Long.MAX_VALUE;
        if (isValidateBST(root, min, max)) {
            System.out.println("Tree is BST");
        } else {
            System.out.println("Tree is not BST");
        }
    }

    public static boolean isValidateBST(TreeNode root, long min, long max) {
        if (root == null)
            return true;

        if (root.val <= min || root.val >= max) {
            return false;
        } else
            return isValidateBST(root.left, min, Long.valueOf(root.val))
                    && isValidateBST(root.right, Long.valueOf(root.val), max);

    }
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;
    }
}

}

// Time Complexity: O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to check for valid
//BST
bool isValidBST(TreeNode *root,long long min1,long long max1)
{
   if(root==NULL)
       return true;
   if(root->data<=min1||root->data>=max1)
       return false;
   return isValidBST(root->left,min1,root->data)
          &&isValidBST(root->right,root->data,max1);
}
bool isValidBST(TreeNode* root) 
{
    return isValidBST(root,LLONG_MIN,LLONG_MAX);
}
int main()
{
    TreeNode *tree=new TreeNode(2);
    tree->left=new TreeNode(1);
    tree->right=new TreeNode(3);
    bool flag=isValidBST(tree);
    if(flag)
       cout<<"Tree is BST\n";
    else
      cout<<"Tree is not BST\n";
    return 0;
}