Validate Binary Search Tree Problem Solution

Validate Binary Search Tree Problem: Given the root of a binary tree, determine if it is a valid binary search tree (BST).

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

Validate Binary Search Tree Problem Solution

Problem Solution In Python

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def inorder(root):
            if root.left:
                inorder(root.left)
            res.append(root.val)
            if root.right:
                inorder(root.right)
        res=[]
        if root:
            inorder(root)
        for i in range(1,len(res)):
            if res[i-1]>=res[i]:
                return False
        return True

Problem Solution In Java

List<Integer> sol = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
	dfs(root);
	for(int i=1; i<sol.size(); i++)
		if(sol.get(i-1)>=sol.get(i))
			return false;
	return true;
}

public void dfs(TreeNode root) {
	if(root==null) return;
	dfs(root.left);
	sol.add(root.val);
	dfs(root.right);
}

Problem Solution In C++

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root,NULL,NULL);
    }
    bool helper(TreeNode* root, TreeNode* min, TreeNode* max)
    {
        if(root==NULL)
            return true;
        else if(min!=NULL && root->val<=min->val || max!=NULL && root->val>=max->val)
            return false;
        else if( helper(root->left, min, root) && helper(root->right, root, max))
            return true;
        return false;
    }
};

Problem Solution In C

bool check(struct TreeNode* root, int* min, int* max) {
    if (root == NULL) {
        return true;
    }
    if ((min != NULL && root->val <= *min) || (max != NULL && root->val >= *max)) {
        return false;
    }
    return check(root->left, min, &root->val) && check(root->right, &root->val, max);
}

bool isValidBST(struct TreeNode* root){
    return check(root, NULL, NULL);
}