Trying to solve "Check for BST" question on GeeksForGeeks but I keep getting wrong errors but I don't think there is an issue with my code. Can someone please look at my code and explain? Thank you.
public class Solution
{
//Function to check whether a Binary Tree is BST or not.
static boolean answer = true;
boolean isBST(Node root)
{
// code here.
if(root==null) return false;
traverseLeft(root.left,root.data);
traverseRight(root.right,root.data);
return answer;
}
void traverseLeft(Node root, int val){
if(root == null) return;
if(root.data >= val){
answer = false;
return;
}
traverseLeft(root.left,root.data);
traverseRight(root.right,root.data);
}
void traverseRight(Node root, int val){
if(root == null) return;
if(root.data <= val){
answer = false;
return;
}
traverseLeft(root.left,root.data);
traverseRight(root.right,root.data);
}
}
There are several issues with your attempt:
result should not be a static variable. As a static variable, its value will survive across different test cases, never resetting to true after the first test has run, and thus possibly giving false negatives.
Instead you should let the recursive function return whether the BST is valid in that particular subtree. The caller should then capture that boolean result for both its children and perform a logical AND to determine what its own response will be: true if, and only when, it is true for both recursive calls for the children and its own value is within the acceptable range. In all other cases it should return false. That way you have no need for a more global variable.
It is not enough to compare a node's value with the value of its parent. For instance, your logic would consider the following tree a valid BST, but it isn't:
6
/
1
\
10
While the value 10 passes the test your code has (it is at least 1), it should also not be greater than 6. So a correct algorithm will pass two limiting values to the recursive calls: a lower limit and an upper limit.