Leetcode Validate Binary Search Tree problem solution

YASH PAL,

In this Leetcode Validate Binary Search Tree problem solution we have Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:

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

coding problems