Two solutions - Recursion and Inorder traversal in Java


  • 0
    G
    Recursive solution using Long values to avoid Integer overflow
    
    public class Solution {
            public boolean isValidBST(TreeNode root) {
                return isValidBSTUtil(root, Long.MAX_VALUE, Long.MIN_VALUE);
            }
            
            public boolean isValidBSTUtil(TreeNode root, long max, long min){
                 if(root==null){
                    return true;
                }
                if(root.val>=max || root.val<=min){
                    return false;
                }
                return isValidBSTUtil(root.left, root.val, min) && isValidBSTUtil(root.right, max, root.val);
            }
        }
    

    Inorder solution which stores the previous value

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

  • 0
    A

    C# solution passing by reference.

    public bool IsValidBST(TreeNode root) {
            TreeNode preMax = null;
            return isValidBST(root, ref preMax); 
        }
        private bool isValidBST(TreeNode root, ref TreeNode preMax){
            if (root==null) { return true; }
            if (!isValidBST(root.left, ref preMax)) { return false; }
            if (preMax!=null && preMax.val>=root.val) { return false; }
            preMax = root;
            return isValidBST(root.right, ref preMax);
        }

Log in to reply
 

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