Validate a Binary Search Tree

Question

I am working on a leetcode problem where I am asked to check whether or not a Binary Search Tree is valid. So far, my solution only passes 58 out 75 test cases. Any pointers on where I went wrong and how to fix it?

Here is the question:

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.

Example 1:

                     2
                    / \
                   1   3

Input: [2,1,3]

Output: true

Example 2:

                     5
                    / \
                   1   4
                      / \
                     3   6

Input: [5,1,4,null,null,3,6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

Here is my Solution:

class Solution {
    public boolean isValidBST(TreeNode root) {
        
        return isValidHelper(root); 
    }
    
    public boolean isValidHelper(TreeNode root)
    {
        if(root == null)
            return true; 
        
        
        isValidHelper(root.left); 
        
 if(root.left != null && !(root.left.val < root.val) || root.right != null && !(root.right.val > root.val))
            return false; 
        
        isValidHelper(root.right); 
        
        return true;
    }
}

Answer 1

Your program fails in cases like this:

     5
   3   7
  1 6

because you only compare the value at the root of the subtrees.

I don't give a fix on purpose. You will learn more finding that out yourself.