Preorder recursive solution with explanation


  • 0
    L

    One should realize that just checking left and right value of a particular node will not work. Deep down some levels, right child of a parent may be bigger than the parent of its parent, thus breaking the BST relationship. It is easy to bound each node using a right and left value so these values get passed on from the top to bottom.

    It will require a preorder traversal. Here is the algorithm:

    1. Check for the lower and upper bounds. Fail if needed
    2. Check the left and right subtrees recursively. Both should return true.
     public boolean isValidBST(TreeNode root) {
            return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
        }
        
        private boolean helper(TreeNode root, long lower, long upper) {
            if(root==null) {
                return true;
            }
            
            if(!(root.val>lower && root.val<upper)) {
                return false;
            }
            
            return helper(root.left,lower,root.val) && helper(root.right,root.val,upper);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.