Check BST balanced

#1

Hello sir/ ma’am,
this is my code for this ques,
Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a 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.

I am unable to handle the case when root->val = INT_MAX or INT_MIN.


(sharing only the main func part)

eg: [2147483647,2147483647] , output should be false, but my code is giving true.

Please tell me where am i doing wrong.

#2

@priyanshi.agarwal3405 hey have corrected your code,few mistakes were there,please check it and feel free to ask any doubt :slight_smile:

#3

Sir, where have you made the changes? I am unable to see them on my public link. Please share the link of the modified code.

#4

@priyanshi.agarwal3405 hey here is updated code:

#5

Sir now it gives runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type ‘int’ for test case [2147483647] i.e. when root->val=INT_MAX.

#6

@priyanshi.agarwal3405 hey where are you submitting send that link please and full code which you are submitting.

#7

I am trying to submit it on LeetCode. Sharing the link::

#8

@priyanshi.agarwal3405 hey ,try submitting this code:
class Solution {
public boolean helper(TreeNode node, int lower,int upper) {
if (node == NULL) return true;

int val = node->val;
if (lower != NULL && val <= lower) return false;
if (upper != NULL && val >= upper) return false;

if (! helper(node->right, val, upper)) return false;
if (! helper(node->left, lower, val)) return false;
return true;

}

public boolean isValidBST(TreeNode root) {
return helper(root, NULL, NULL);
}
}

#9

Yeah I also saw this code in the solutions section of this problem. I tried to run this. Still all test cases not passing. eg: [0,null,-1] …Also can’t this ques be done using the approach that Prateek bhaiya told in his video??

#10

@priyanshi.agarwal3405 hey actually in leetcode corner test cases are also there which are very strong ,so you have to handle them maually like some take root->val+1 in recursion or some take root->val in recursion,so that you have to see.
you can see this code:

class Solution {
public:
	vector<int> in;
	bool isValidBST(TreeNode* root) {
		if (root == NULL)
			return true;
		if (!isValidBST(root->left))
			return false;
		if (!in.empty() && in.back() >= root->val)
			return false;
		in.push_back(root->val);
		if (!isValidBST(root->right))
			return false;
		return true;
	}
};
#11

Yeah okay, got it. Thanks.

#12

@priyanshi.agarwal3405 your welcome.