Hi I am a beginner and learning DSA now. This program is to validate a bst. In the image attached all the left nodes are lesser than their root node and all the right nodes are greater than the their root node. But expected output is false according to the compiler(leet code) and i dont understand why. Can someone explain this to me pls. Also please find below my code.
class Solution {
public boolean validatebst(TreeNode root){
System.out.println("Traversing "+ root.val);
if(root.left !=null && root.left.val > root.val)
return false;
else if(root.right != null && root.right.val < root.val){
return false;
}
return true;
}
public boolean checkbst(TreeNode root){
if(root == null)
return true;
if(!this.checkbst(root.left))
return false;
if(!this.validatebst(root))
return false;
if(!this.checkbst(root.right))
return false;
return true;
}
public boolean isValidBST(TreeNode root) {
if(this.checkbst(root))
return true;
return false;
}
}
The tree is not valid because you have a leaf on the right side that is less than the root. Even though it is on the left of its parent, which is correct, everything to the right of the root must be greater than the root.
https://dev.to/adityavardhancoder/what-is-a-valid-binary-search-tree-4kgj Example 3 in this link explains, hope this helps :)