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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment