98.Validate Binary Search Tree

See also

94.Binary Tree Inorder Traversal

230.Kth Smallest Element in a BST

https://leetcode.com/problems/validate-binary-search-tree/discuss/32112/

1-DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean dfs(TreeNode root, Long min, Long max){
        if(root == null){
            return true;
        }     
        if(root.val <= min || root.val >= max){
            return false;
        }
        boolean isLeftValid = dfs(root.left, min, root.val + 0L);
        boolean isRightValid = dfs(root.right, root.val + 0L, max);
        return isLeftValid && isRightValid;
    }
    public boolean isValidBST(TreeNode root) {
        Long min = Integer.MIN_VALUE - 1L;
        Long max = Integer.MAX_VALUE + 1L;
        return dfs(root, min, max);
    }
}

2- Inorder Traversal Using Stack

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null)
            return true;
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(pre != null && pre.val >= root.val)
                return false;
            pre = root;
            root = root.right;
        }
        return true;
    }
}